Fault tolerant topology control for one-to-all communications in symmetric wireless networks
This paper introduces the problem of fault tolerant topology control for one-to-all communications in symmetric wireless networks. We investigate two algorithms to address the problem, namely Minimum Weight-Based Algorithm (MWBA) and Nearest Neighbour Augmentation Algorithm (NNAA) and prove that the former is a 4k approximation and the latter is a (k + 4) approximation. Through simulations, we evaluate the average performance of these two algorithms and find that MWBA is slightly better than NNAA in terms of the total power consumption.

title: Optimization scheme for sensor coverage scheduling with bandwidth constraints
abstract: 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).

title: On the construction of 2-connected virtual backbone in wireless networks
abstract: 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.

title: Coverage problems in wireless sensor networks: designs and analysis
abstract: 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.

title: 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. ( 2006).

title: Greedy Approximation Algorithms
abstract: 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.

title: OBFS: A File System for Object-Based Storage Devices
abstract: 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.

title: File System Workload Analysis For Large Scientific Computing Applications
abstract: Parallel scientific applications require high-performance I/O support from underlying file systems. A comprehensive understanding of the expected workload is therefore essential for the design of high-performance parallel file systems. We re-examine the workload characteristics in parallel computing environments in the light of recent technology advances and new applications. We analyze application traces from a cluster with hundreds of nodes. On average, each application has only one or two typical request sizes. Large requests from several hundred kilobytes to several megabytes are very common. Although in some applications small requests account for more than 90% of all requests, almost all of the I/O data are transferred by large requests. All of these applications show bursty access patterns. More than 65% of write requests have inter-arrival times within one millisecond in most applications. By running the same benchmark on different file models, we also find that the write throughput of using an individual output file for each node exceeds that of using a shared file for all nodes by a factor of 5. This indicates that current file systems are not well optimized for file sharing.

title: Dependability analysis of nano-scale FinFET circuits
abstract: FinFET technology has been proposed as a promising alternative for deep sub-micro bulk CMOS technology, because of its better scalability. Previous works have studied the performance or power advantages of FinFET circuits over bulk CMOS circuits. This paper provides the dependability analysis of FinFET circuits, studying the soft error vulnerability of FinFET circuits and the impact of process variation. Our experiments compare FinFET circuits against bulk CMOS circuits in both 32 nm and 45 nm technologies, showing that FinFET circuits have better dependability and scalability, which is indicated by better soft error immunity and less impact of process variation. It is concluded that FinFET-based circuit design is more robust than the bulk CMOS based circuit design

title: Variation-aware resource sharing and binding in behavioral synthesis
abstract: As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep submicron designs. In the presence of process variations, worst-case timing analysis may lead to overly conservative synthesis, and may end up using excess resources to guarantee design constraints. In this paper, we propose an efficient variation-aware resource sharing and binding algorithm in behavioral synthesis, which takes into account the performance variations for functional units. The performance yield, which is defined as the probability that the synthesized hardware meets the target performance constraints, is used to evaluate the synthesis result. An efficient metric called statistical performance improvement, is used to guide resource sharing and binding. The proposed algorithm is evaluated within a commercial synthesis framework that generates optimized RTL netlists from behavioral specifications. The effectiveness of the proposed algorithm is demonstrated with a set of industrial benchmark designs, which consist of blocks that are commonly used in wireless and image processing applications. The experimental results show that our method achieves an average 33% area reduction over traditional methods, which are based on the worst-case delay analysis, with an average 10% run time overhead.

title: Variability-driven module selection with joint design time optimization and post-silicon tuning
abstract: Increasing delay and power variation are significant challenges to the designers as technology scales to the deep sub-micron (DSM) regime. Traditional module selection techniques in high level synthesis use worst case delay/power information to perform the optimization, and therefore may be too pessimistic such that extra resources are used to guarantee design requirements. Parametric yield, which is defined as the probability of the synthesized hardware meeting the performance/power constraints, can be used to guide design space exploration. The parametric yield can be effectively improved by combining both design-time variation-aware optimization and post silicon tuning techniques (such as adaptive body biasing (ABB)). In this paper, we propose a module selection algorithm that combines design-time optimization with post- silicon tuning (using ABB) to maximize design yield. A variation-aware module selection algorithm based on efficient performance and power yield gradient computation is developed. The post silicon optimization is formulated as an efficient sequential conic program to determine the optimal body bias distribution, which in turn affects design-time module selection. The experiment results show that significant yield can be achieved compared to traditional worst-case driven module selection technique. To the best of our knowledge, this is the first variability-driven high level synthesis technique that considers post-silicon tuning during design time optimization.