Research

Yujie He, Wenlin Chen, Yixin Chen

This paper introduces a supervised metric learning algorithm, called kernel density metric learning (KDML), which is easy to use and provides nonlinear, probability-based distance measures. KDML constructs a direct nonlinear mapping from the original input space into a feature space based on kernel density estimation. The nonlinear mapping in KDML embodies established distance measures between probability density functions, and leads to correct classification on datasets for which linear metric learning methods would fail. Existing metric learning algorithms, such as large margin nearest neighbors (LMNN), can then be applied to the KDML features to learn a Mahalanobis distance. We also propose an integrated optimization algorithm that learns not only the Mahalanobis matrix but also kernel bandwidths, the only hyper-parameters in the nonlinear mapping. KDML can naturally handle not only numerical features, but also categorical ones, which is rarely found in previous metric learning algorithms. Extensive experimental results on various benchmark datasets show that KDML significantly improves existing metric learning algorithms in terms of kNN classification accuracy.

Bo Li

Wireless Structural Control (WSC) systems can play a crucial role in protecting civil infrastructure in the event of earthquakes and other natural disasters. Such systems represent an exemplary class of cyber-physical systems that perform close-loop control using wireless sensor networks. Existing WSC research usually employs wireless sensors installed on small lab structures, which cannot capture realistic delays and data loss in wireless sensor networks deployed on large civil structures. The lack of realistic tools that capture both the cyber (wireless) and physical (structural) aspects of WSC systems has been a hurdle for cyber-physical systems research for civil infrastructure. This advances the state of the art through the following contributions. First, we developed the Wireless Cyber-Physical Simulator (WCPS), an integrated environment that combines realistic simulations of both wireless sensor networks and structures. WCPS integrates Simulink and TOSSIM, a state-of-the-art sensor network simulator featuring a realistic wireless model seeded by signal traces. Second, we performed two realistic case studies each combining a structural model with wireless traces collected from real-world environments. The building study combines a benchmark building model and wireless traces collected from a multi-story building. The bridge study combines the structural model of the Cape Girardeau bridge over the Mississippi River and wireless traces collected from a similar bridge (the Jindo Bridge) in South Korea. These case studies shed light on the challenges of WSC and the limitations of a traditional structural control approach under realistic wireless conditions. Finally, we proposed a cyber-physical co-design approach to WSC that integrates a novel holistic scheduling scheme (for sensing, communication and control) and an Optimal Time Delay Controller (OTDC) that substantially improves structural control performance.

Minmin Chen

The generalization properties of most existing machine learning techniques are predicated on the assumptions that 1) a sufficiently large quantity of training data is available; 2) the training and testing data come from some common distribution. Although these assumptions are often met in practice, there are also many scenarios in which training data from the relevant distribution is insufficient. We focus on making use of additional data, which is readily available or can be obtained easily but comes from a different distribution than the testing data, to aid learning.
We present five learning scenarios, depending on how the distribution we used to sample the additional training data differs from the testing distribution: 1) learning with weak supervision; 2) domain adaptation; 3) learning from multiple domains; 4) learning from corrupted data; 5) learning with partial supervision.
We introduce two strategies and manifest them in five ways to cope with the difference between the training and testing distribution. The first strategy, which gives rise to Pseudo Multi-view Co-training (PMC) and Co-training for Domain Adaptation (CODA), is inspired by the co-training [23] algorithm for multi-view data. PMC generalizes co-training to the more common single view data and allows us to learn from weakly labeled data retrieved free from the web. CODA integrates PMC with an another feature selection component to address the feature incompatibility between domains for domain adaptation. PMC and CODA are evaluated on a variety of real datasets, and both yield record performance.
The second strategy marginalized dropout leads to marginalized Stacked Denoising Autoencoders (mSDA), Marginalized Corrupted Features (MCF) and FastTag (FastTag). mSDA diminishes the difference between distributions associated with different domains by learning a new representation through marginalized corruption and reconstruciton. MCF learns from a known distribution which is created by corrupting a small set of training data, and improves robustness of learned classifiers by training on "infinitely" many data sampled from the distribution. FastTag applies marginalized dropout to the output of partially labeled data to recover missing labels for multi-label tasks. These three algorithms not only achieve the state-of-art performance in various tasks, but also deliver orders of magnitude speed up at training and testing comparing to competing algorithms.

William D. Richard, Ph.D.

Upsampling is required prior to the summation step in most receive digital beamforming implementations to produce an accurate summed RF line or vector.  This is true in both annular and linear array systems where receive echos are digitized first and then time delayed in the digital domain to achieve proper signal alignment.  The efficient, parallel, real-time upsampling circuit presented here produces M upsampled values per ADC clock, where M is the desired upsampling factor.  A circuit implementation that upsamples by a factor of M=4 is presented as an example of the more general technique.

Jing Li, Kunal Agrawal, Chenyang Lu, Christopher Gill
Department of Computer Science and Engineering
Washington University in St. Louis
St. Louis, MO, USA

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. We prove that a Global Earliest Deadline First (GEDF) scheduling policy provides a capacity augmentation bound of 4-2/m and a resource augmentation bound of 2-1/m for parallel tasks in the general directed acyclic graph model. For the proposed capacity augmentation bound of 4-2/m for implicit deadline tasks under GEDF, we prove that if a task set has a total utilization of at most m/(4-2/m) and each task’s critical path length is no more than 1/(4-2/m) of its deadline, it can be scheduled on a machine with m processors under GEDF. Our capacity augmentation bound therefore can be used as a straightforward schedulability test. For the standard resource augmentation bound of 2-1/m for arbitrary deadline tasks under GEDF, we prove that if an ideal optimal scheduler can schedule a task set on m unit-speed processors, then GEDF can schedule the same task set on m processors of speed 2-1/m. However, this bound does not lead to a schedulabilty test since the ideal optimal scheduler is only hypothetical and is not known. Simulations confirm that the GEDF is not only safe under the capacity augmentation bound for various randomly generated task sets, but also performs surprisingly well and usually outperforms an existing scheduling technique that involves task decomposition.

Xiang Zhou

Recent advances in High-Throughput Sequencing (HTS) technology have greatly facilitated the researches in bioinformatics field. With the ultra-high sequencing speed and improved base-calling accuracy, Illumina Genome Analyzer is currently the most widely used platform in the field. To use the raw reads generated from the sequencing machine, the 3’ adapter sequence attached to the real read in the process of ligation needs to be correctly trimmed. This is often done by some inhouse scripts or different packages with various parameters. They either use the Smith-Waterman algorithm or search for an exact match of the 3’ adapter sequence.

In this report, I investigated methodologies as well as the strengths and weaknesses of five representative mainstream adapter trimming tools in order to suggest a direction for other researchers. Furthermore, four sets of detailed analysis were performed to evaluate the performances of these tools. I demonstrated that my adapter trimming method is flexible, accurate and efficient for Next Generation Sequencing (NGS) analysis.

Collin Foster

Recent breakthroughs in nanofabrication techniques have led to development of sophisticated Division-of-Focal-Plane (DoFP) polarization imaging sensors. One such technique allows the fabrication of nanowire filters fabricated directly on the imaging sensor itself. This technique can be used to fabricate robust DoFP polarization imaging sensors. However, the polarization information captured by the imagers can be degraded due to imperfections in the fabrication of the nanowire filters on the imaging sensor. Polarization information can also be degraded from other sources including crosstalk between pixels. To compensate for these undesired effects, a calibration routine can be applied to each pixel after image capture. In this project, we implement a calibration routine as a step in the pipeline processing of captured polarization images. The polarization image processing and calibration are implemented on an FPGA development board to achieve a real-time response to image captures.

David Shelley

Most high-fidelity digital cameras currently available obtain their images using technology where individual pixels can only acquire a single color. Since the acquisition of multiple colors is necessary to capture a full colored image, picture resolution is lost due to difficulties in interpolation between non-adjacent, same color pixels. The resulting unsharp images create the need to find a new way to obtain these images without requiring interpolation between adjacent pixels.

An innovative method to capture images with individual pixel cells consisting of three layers of photodetectors stacked vertically upon one another has been created to rectify this problem, but no complete camera system has been fabricated to date. This project integrates a stacked photo detector imager chip into a complete camera, allowing full functionality and control of the photo detector chip to a personal computer. A six layer printed circuit board is fabricated using Cadence Allegro, firmware is written and compiled using Xilinx ISE and software is written in Microsoft Visual Studio 2010.

Sisu Xi, Chong Li, Chenyang Lu, and Christopher Gill

As computer hardware becomes increasingly powerful, there is an ongoing trend towards integrating complex, legacy real-time systems using fewer hosts through virtualization. Especially in embedded systems domains such as avionics and automotive engineering, this kind of system integration can greatly reduce system weight, cost, and power requirements. When systems are integrated in this manner, \emph{network communication} may become local \emph{inter-domain communication} (IDC) within the same host. This paper examines the limitations of inter-domain communication in Xen, a widely used open-source virtual machine monitor (VMM) that recently has been extended to support real-time domain scheduling. We find that both the VMM scheduler and the manager domain can significantly impact real-time IDC performance under different conditions, and show that improving the VMM scheduler alone cannot deliver real-time performance for local IDC. To address those limitations, we present the RTCA, a Real-Time Communication Architecture within the manager domain in Xen, along with empirical evaluations whose results demonstrate that the latency of communication tasks can be improved dramatically from ms to $\mu$s by a combination of the RTCA and a real-time VMM scheduler.

Abusayeed Saifullah

Self-stabilization is a theoretical framework of non-masking fault-tolerance for distributed networks. A self-stabilizing system is capable of tolerating any unexpected transient fault without outside intervention and, regardless of the initial state, it can converge to a legitimate global state, a predefined vector of local states, in finite time. Self-stabilization has rendered a good problem solving paradigm of networks over the last decade. In this paper, we survey the self-stabilizing solutions for various network optimization problems such as network flow, load balancing, load and resource distribution, routing, file distribution, shortest paths etc. The paper  also summarizes some recent works presenting how the convergence of a self-stabilizing distributed network can be modelled as a convex optimization problem with the exploitation of an analogy between self-stabilizing systems and stable feedback systems. The works pertaining to gradient adaptation of self-stabilizing system are also presented.

Xuefeng Zhou

Post-transcriptional gene regulation at the RNA level has been recently shown to be more widespread and important than previously assumed. While various regulatory RNA molecules have been reported in animals and plants, two prominent types of regulatory small RNAs are microRNAs (miRNAs) and endogenous short interfering RNAs (siRNAs). Because of their importance, their nature and the difficulties in studying them, research in miRNAs has been an active research topic with many computational challenges.

First, computational strategies for miRNA identification have been developed to overcome the technical hurdles for experimental methods based on expression screening. We propose and develop a novel ranking algorithm based on random walks to computationally predict novel miRNAs from genomes, which have a few known miRNAs, may be poorly annotation and even not completely assembled. We also develop meta-feature based classification method to identify miRNAs from high-throughput sequencing data of small RNAs. In addition, we devise a pipeline to analyze natsiRNA in high-throughput sequencing data.

Secondly, we formulate the problem of promoter prediction based on multiple instance learning scheme, and propose an effective promoter identification algorithm, called CoVote. We apply CoVote to predict microRNA core promoters. We investigate core promoter regions of microRNA genes in Caenorhabditis elegans, Homo sapiens, Arabidopsis thaliana and Oryza sativa, and further analyze sequence motifs in the putative core promoters which may be involved in the transcription of microRNA genes.

Furthermore, with characterized promoters of miRNA genes, we apply data mining approaches to model the transcriptome of miRNAs under particular conditions. Additionally, by integrating miRNA target genes, we further analyze the miRNA-mediate regulatory networks and computationally identify network motifs. Since miRNAs and their targets can be formulated as a natural bipartite network(graph), we propose and develop a tool to study modules in the miRNA-regulatory network.

Ross Sowell

Magnetic resonance imaging (MRI) and computed tomography (CT) scanners have long been used to produce three-dimensional (3D) samplings of anatomy elements for use in medical visualization and analysis. From such data sets, physicians often need to construct surfaces representing anatomical shapes in order to conduct treatment, such as irradiating a tumor. Traditionally, this is done through a time-consuming and error-prone process in which an experienced scientist or physician marks a series of parallel contours that outline the structures of interest. Recent advances in surface reconstruction algorithms have led to methods for reconstructing surfaces from nonparallel contours that could greatly reduce the manual component of this process. Despite these technological advances, the segmentation process has remained unchanged.

This dissertation takes the first steps toward bridging the gap between the new surface reconstruction technologies and bringing those methods to use in clinical practice. We develop VolumeViewer [68], a novel interface for modeling surfaces from volume data by allowing the user to sketch contours on arbitrarily oriented cross-sections of the volume. We design the algorithms necessary to support nonparallel contouring, and we evaluate the system with medical professionals using actual patient data. In this way, we begin to understand how nonparallel contouring can aid the segmentation process and expose the challenges associated with a nonparallel contouring system in practice.

Huang-Ming Huang

Traditional fixed-priority scheduling analysis for periodic/sporadic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and estimates of tasks’ worst case execution times must be conservative in case a task runs longer than is usual. To address the significant under-utilization of a system’s resources under normal operating conditions that can arise from these assumptions, several mixed-criticality scheduling approaches have been proposed. However, to date there has been no quantitative comparison of system schedulability or run-time overhead for the different approaches.

In this dissertation, we present what is to our knowledge the first side-by-side implementation and evaluation of those approaches, for periodic and sporadic mixed-criticality tasks on uniprocessor or distributed systems, under a mixed-criticality scheduling model that is common to all these approaches. To make a fair evaluation of mixed-criticality scheduling, we also address some previously open issues and propose modifications to improve schedulability and correctness of particular approaches.

To facilitate the development and evaluation of mixed-criticality applications, we have designed and developed a distributed real-time middleware, called MCFlow, for mixed-criticality end-to-end tasks running on multi-core platforms. The research presented in this dissertation provides the following contributions to the state of the art in real-time middleware: (1) an efficient component model through which dependent subtask graphs can be configured flexibly for execution within a single core, across cores of a common host, or spanning multiple hosts; (2) support for optimizations to inter-component communication to reduce data copying without sacrificing the ability to execute subtasks in parallel; (3) a strict separation of timing and functional concerns so that they can be configured independently; (4) an event dispatching architecture that uses lock free algorithms where possible to reduce memory contention, CPU context switching, and priority inversion; and (5) empirical evaluations of MCFlow itself and of different mixed criticality scheduling approaches both with a single host and end-to-end across multiple hosts. The results of our evaluation show that in terms of basic distributed real-time behavior MCFlow performs comparably to the state of the art TAO real-time object request broker when only one core is used and outperforms TAO when multiple cores are involved. We also identify and categorize different use cases under which different mixed criticality scheduling approaches are preferable.

Devorah Langsam

Capturing imagery from outdoor cameras provides a large amount of information about a scene. The true surface appearances of elements in a scene, however, are often incorrectly represented in images. To get a better representation of the scene it is necessary to separate the effects of the underlying reflectance, illumination, and fog in the image. The goal of the dark channel prior is to eliminate the effects of haze in outdoor images and recover the true surface reflectance image for the scene.

Jed Jackoway

The goal of the project was to reconstruct the skeleton of a Microsoft Kinect user’s hand. Out of the box, Kinect reconstruct the skeleton of users’ bodies, but it only does large joints, such that the hand is given a location on the general skeleton, but the specifics of the fingers and fist are not actually calculated.

Brian Haynes

This dissertation addresses a current outstanding problem in the field of systems biology, which is to identify the structure of a transcriptional network from high-throughput experimental data. Understanding of the connectivity of a transcriptional network is an important piece of the puzzle, which relates the genotype of an organism to its phenotypes. An overwhelming number of computational approaches have been proposed to perform integrative analyses on large collections of high-throughput gene expression datasets to infer the structure of transcriptional networks. I put forth a methodology by which these tools can be evaluated and compared against one another to better understand their strengths and weaknesses. Next I undertake the task of utilizing high-throughput datasets to learn new and interesting network biology in the pathogenic fungus Cryptococcus neoformans. Finally I propose a novel computational method for mapping out transcriptional networks that unifies two orthogonal strategies for network inference. I apply this method to map out the transcriptional network of Saccharomyces cerevisiae and demonstrate how network inference results can complement chromatin immunoprecipitation (ChIP) experiments, which directly probe the binding events of transcriptional regulators. Collectively, my contributions improve both the accessibility and practicality of network inference methods.

Zhicheng Yang

In this project, we continued Dr. Chipara's study, which developed an early warning system (EWS) to detect the vital signs of patients in order to help doctors to intervene in time [1]. Since the number of wards increased, the environment our system faced with became more complicated and our network became more sensitive. This project focused on finding reasons on the relays that didn't work and doing a reliability analysis on the network in one ward our study covered.

Benjamin Wun

High speed networking is a demanding task that has traditionally been performed in dedicated, purpose built hardware or specialized network processors. These platforms sacrifice flexibility or programmability in favor of performance. Recently, there has been much interest in using multi-core general purpose processors, which have the advantages of being easily programmable and upgradeable. The best way to exploit these new architectures for networking is an open question that has been the subject of much recent research. In this disseration, I explore the best way to exploit multicore general purpose processors for packet processing applications. This includes both new architectural organizations for the processors as well as changes to the systems software. I intend to demonstrate the efficacy of these techniques by using them to build an open and extensible network security and monitoring platform that can out perform existing solutions.

Terry Tidwell

Time utility functions offer a reasonably general way to describe the complex timing constraints of real-time and cyber-physical systems. However, utility-aware scheduling policy design is an open research problem. In particular, scheduling policies that optimize expected utility accrual are needed for real-time and cyber-physical domains.
This dissertation addresses the problem of utility-aware scheduling for systems with periodic real-time task sets and stochastic non-preemptive execution intervals. We model these systems asMarkov Decision Processes. This model provides an evaluation framework by which different scheduling policies can be compared. By solving the Markov Decision Process we can derive value-optimal scheduling policies for moderate sized problems.
However, the time and memory complexity of computing and storing value-optimal scheduling policies also necessitates the exploration of other more scalable solutions. We consider heuristic schedulers, including a generalization we have developed for the existing Utility Accrual Packet Scheduling Algorithm. We compare several heuristics under soft and hard real-time conditions, different load conditions, and different classes of time utility functions. Based on these evaluations we present guidelines for which heuristics are best suited to particular scheduling criteria.
Finally, we address the memory complexity of value-optimal scheduling, and examine trade-offs between optimality and memory complexity. We show that it is possible to derive good low complexity scheduling decision functions based on a synthesis of heuristics and reduced-memory approximations of the value-optimal scheduling policy.

Abusayeed Saifullah, David Ferry, Kunal Agrawal, Chenyang Lu, and Christopher Gill

Due to their potential to deliver increased performance over single-core processors, multi-core processors have become mainstream in processor design. Computation-intensive real-time systems must exploit intra-task parallelism to take full advantage of multi-core processing. However, existing results in real-time scheduling of parallel tasks focus on restrictive task models such as the synchronous model where a task is a sequence of alternating parallel and sequential segments, and parallel segments have threads of execution that are of equal length. In this paper, we address a general model for deterministic parallel tasks, where a task is represented as a DAG with different nodes having different execution requirements. We make several key contributions towards both preemptive and non-preemptive realtime scheduling of DAG tasks on multi-core processors. First, we propose a task decomposition that splits a DAG into sequential tasks. Second, we prove that parallel tasks, upon decomposition, can be scheduled using preemptive global EDF with a resource augmentation bound of 4. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. Third, we prove that the decomposition has a resource augmentation bound of 4 plus a non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for nonpreemptive scheduling of parallel tasks. Through simulations, we demonstrate that the achieved bounds are safe and sufficient.

Cindy Grimm and Pushkar Joshi

We present a system for sketching in 2D to create 3D curves. The interface is light-weight, pen-based, and based on observations of how artists sketch on paper.

Logan Stafman

Forest is an overlay network designed for large real-time distributed systems.  In particular, we’re interested in virtual worlds that provide high-quality interaction over a constantly changing pattern of communication.  Forest is suitable for applications in which many entities send data to a large set of constantly changing entities.  By using tree-structured channels, we can create logically isolated private networks which support both unicast and multicast routing.  In this paper, we will discuss the core components of Forest and measure the performance of the control elements of the network. We will also provide examples of control sequences and the roles played by control elements in those sequences to help maintain fast, reliable data delivery.

Adam Kraft

As cellular phones grow faster and become equipped with better sensors, consumers are seeing a rise in augmented reality applications available on their mobile devices. Sports augmented reality is one area that is projected to grow over the next couple of years. We aim to build an application intended for use at a live baseball game. Our application optimizes a best-fit homography to locate the structure of the playing field. From there, we are able to visualize information and statistics directly onto the user's mobile device. This is accomplished in real time, requiring minimal input from the user.

Abdel-Karim Al-Tamimi

Video streaming traffic has been surging in the last few years, which has resulted in an increase of its Internet traffic share on a daily basis. The importance of video streaming management has been emphasized with the advent of High Definition (HD) video streaming, as it requires by its nature more network resources.

In this dissertation, we provide a better support for managing HD video traffic over both wireless and wired networks through several contributions. We present a simple, general and accurate video source model: Simplified Seasonal ARIMA Model (SAM). SAM is capable of capturing the statistical characteristics of video traces with less than 5% difference from their calculated optimal models. SAM is shown to be capable of modeling video traces encoded with MPEG-4 Part2, MPEG-4 Part10, and Scalable Video Codec (SVC) standards, using various encoding settings.

We also provide a large and publicly-available collection of HD video traces along with their analyses results. These analyses include a full statistical analysis of HD videos, in addition to modeling, factor and cluster analyses. These results show that by using SAM, we can achieve up to 50% improvement in video traffic prediction accuracy. In addition, we developed several video tools, including an HD video traffic generator based on our model. Finally, to improve HD video streaming resource management, we present a SAM-based delay-guaranteed dynamic resource allocation (DRA) scheme that can provide up to 32.4% improvement in bandwidth utilization.

Huang-Ming Huang, Christopher Gill, Chenyang Lu

Traditional fixed-priority scheduling analysis for periodic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and estimates of tasks’ worst case execution times must be conservative in case a task runs longer than is usual. To address the significant under-utilization of a system’s resources under normal operating conditions that can arise from these assumptions, three main approaches have been proposed: priority assignment, period transformation, and zero-slack scheduling. However, to date there has been no quantitative comparison of system schedulability or run-time overhead for the different approaches. In this paper, we present what is to our knowledge the first side-by-side evaluation of those approaches, for periodic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all three approaches. To make a fair evaluation of zero-slack scheduling, we also address two previously open issues: how to accommodate execution of a task after its deadline, and how to account for previously unidentified forms of interference between mixed-criticality tasks. Our simulations show that while priority assignment and period transformation are most likely to be able to schedule a randomly selected task set, a small fraction of the task sets are schedulable only under the zero-slack approach. Our empirical evaluation demonstrates that user-space implementations of mechanisms to enforce period transformation and zero-slack scheduling can be achieved on Linux without kernel modification, with suitably low overhead for mixed-criticality real-time task sets.

Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen

WirelessHART is a new standard specifically designed for real-time and reliable communication between sensor and actuator devices for industrial process monitoring and control applications. End-to-end communication delay analysis for WirelessHART networks is required to determine the schedulability of real-time data flows from sensors to actuators for the purpose of acceptance test or workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We then exploit the response time analysis for multiprocessor scheduling and propose a novel method for the delay analysis that establishes an upper bound of the end-to-end communication delay of each real-time flow in a WirelessHART network. Simulation studies based on both random topologies and real network topologies of a 74-node physical wireless sensor network testbed demonstrate that our analysis provides safe and reasonably tight upper bounds of the end-to-end delays of real-time flows, and hence enables effective schedulability tests for WirelessHART networks.

Ezekiel Maier, Randall H Brown, and Michael R Brent

Determining the beginning and end positions of each exon in each protein coding gene within a genome can be difficult because the DNA patterns that signal a gene’s presence have multiple weakly related alternate forms and the DNA fragments that comprise a gene are generally small in comparison to the size of the genome. In response to this challenge, automated gene predictors were created to generate putative gene structures.  N SCAN identifies gene structures in a target DNA sequence and can use conservation patterns learned from alignments between a target and one or more informant DNA sequences. N SCAN uses a Bayesian network, generated from a phylogenetic tree, to probabilistically relate the target sequence to the aligned sequence(s).  Phylogenetic substitution models are used to estimate substitution likelihood along the branches of the tree.  
     Although N SCAN’s predictive accuracy is already a benchmark for de novo HMM based gene predictors, optimizing its use of substitution models will allow for improved conservation pattern estimates leading to even better accuracy. Selecting optimal substitution models requires avoiding overfitting as more detailed models require more free parameters; unfortunately, the number of parameters is limited by the number of known genes available for parameter estimation (training). In order to optimize substitution model selection, we tested eight models on the entire genome including General, Reversible, HKY, Jukes-Cantor, and Kimura. In addition to testing models on the entire genome, genome feature based model selection strategies were investigated by assessing the ability of each model to accurately reflex the unique conservation patterns present in each genome region. Context dependency was examined using zeroth, first, and second order models. All models were tested on the human and D. melanogaster genomes.  Analysis of the data suggests that the nucleotide equilibrium frequency assumption (denoted as πi) is the strongest predictor of a model’s accuracy, followed by reversibility and transition/transversion inequality.  Furthermore, second order models are shown to give an average of 0.6% improvement over first order models, which give an 18% improvement over zeroth order models. Finally, by limiting parameter usage by the number of training examples available for each feature, genome feature based model selection better estimates substitution likelihood leading to a significant improvement in N SCAN’s gene annotation accuracy.  

Abusayeed Saifullah,  You Xu,   Chenyang Lu,   and Yixin Chen

Interference between concurrent transmissions can cause severe performance degradation in wireless sensor networks (WSNs). While multiple channels available in WSN technology such as IEEE 802.15.4 can be exploited to mitigate interference, channel allocation can have a significant impact on the performance of multi-channel communication. This paper proposes a set of distributed algorithms for near-optimal channel allocation in WSNs with theoretical bounds.  We first consider the problem of minimizing the number of channels needed to remove interference in a WSN, and propose both receiver-based and link-based distributed channel allocation protocols. For WSNs with an insufficient number of channels, we formulate a fair channel allocation problem whose objective is to minimize the maximum  interference (MinMax) experienced by any transmission link in the network. We prove that MinMax channel allocation is NP-hard and propose a  distributed link-based MinMax channel allocation protocol. We also propose a distributed protocol for link scheduling based on MinMax channel allocation. Simulations based on  real topologies  and data traces collected from a WSN testbed consisting of  74 TelosB motes, and using random topologies  have shown that our channel allocation protocols significantly outperform  a state-of-the-art channel allocation protocol.

Jeremy Buhler, Kunal Agrawal, Peng Li, Roger D. Chamberlain

In this report, we show that deadlock avoidance for
streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first give efficient algorithms for dummy interval computation in series-parallel DAGs, then generalize our results to a larger graph family, the CS4DAGs, in which every undirected cycle has exactly one source and one sink.  Our results show that, for a large set of application
topologies that are both intuitively useful and formalizable, the
streaming model with filtering can be implemented safely with
reasonable compilation overhead.

Christopher Thomas

Simulation is a powerful tool for analysis and improvement of networking technologies, and many simulation packages are available.  One that is growing in popularity is NS-3, the successor to the popular NS-2.  It is a significant departure from NS-2, and offers many advantages and disadvantages.  In this thesis, we translate and update a sophisticated WiMAX simulation model from NS-2 to NS-3, and use this experience to investigate the major differences between NS-2 and NS-3, and the relative strengths of each package.  We then use the NS-3 simulation model to provide analysis on a new WiMAX OFDMA downlink subframe mapping algorithm.

Advisor: Raj Jain

Clifton M. Carey, Jr.

Copy Number Variations (CNVs) are a significant source of human genetic diversity and are believed to be responsible for a wide variety of phenotypic variation. Recent advances in microarray-based genomic hybridization techniques have facilitated CNV analysis as a viable diagnostic technique in the clinic, and several public databases of well-characterized CNVs are being compiled, but a standard for interpreting uncharacterized CNVs has yet to emerge.

This thesis examines the clinical interpretation of uncharacterized CNVs as a multiple instance binary classification problem. We analyze the current state of clinical techniques, then present and test a novel, statistical approach to the problem.

Matthew Klein

N/A

Alex S. Broad

This project focuses on using Reinforcement Learning to optimize arm dynamics through muscle control for desired trajectories. The goal of this project was to create a tool that can be used to gain a better understanding of the arm’s muscles and collect information that is useful in many other disciplines such as biomechanics, anthropology, medicine and robotics. I developed biologically realistic models of primate arm's using Stanford’s SimTK software, an open-source tool for modeling musculoskeletal structures. I then made use of Differential Dynamic Programming in order to generate novel movements from first principles and optimize motion over a specified trajectory. Lastly, I demonstrated the usefulness of this tool by examining its effectiveness in discovering the consequences of different muscle groups on the optimal behavior policy.

Yong Fu¤, Nicholas Kottenstette†, Chenyang Lu¤, Xenofon D. Koutsoukos

Real-time systems face significant challenges in thermal management with their adoption of modern multicore processors. While earlier research on feedback thermal control has shown promise in dealing with the uncertainties in the thermal characteristics, multicore processors introduce new challenges that cannot be handled by previous solutions designed for single-core processors. Multicore processors require the temperatures and real-time performance of multiple cores to be controlled simultaneously, leading to multi-input-multi-output (MIMO) control problems with inter-core thermal coupling. Furthermore, current Dynamic Voltage and Frequency Scaling (DVFS) mechanisms only support a finite set of states, leading to discrete control variables that cannot be handled by standard linear control techniques. This paper presents Real-Time Multicore Thermal Control (RT-MTC), the first feedback thermal control framework specifically designed for multicore real-time systems. RT-MTC dynamically enforces both the temperature and the CPU utilization bounds of a multicore processor through DVFS with discrete frequencies. RT-MTC employs a highly efficient controller that integrates saturation and proportional control components rigorously designed to enforce the desired core temperature and CPU utilization bounds. It handles discrete frequencies through a PulseWidth Modulation (PWM) that achieves effective thermal control by manipulating the dwelling time of discrete frequencies. As a result RT-MTC can achieve effective thermal control with only a small number of frequencies typical in current processors. The robustness and advantages of RTMTC over existing thermal control approaches are demonstrated through extensive simulations under a wide range of uncertainties in term of power consumption.

Daniel A. Lazewatsky and William D. Smart

Most commercially-available robots are either aimed at the research community, or are designed with a single purpose in mind.  The extensive hobbyist community has tended to focus on the hardware and the low-level software aspects.  We claim that there is a need for a low-cost, general-purpose robot, accessible to the hobbyist community, with sufficient computation and sensing to run ``research-grade'' software.  In this paper, we describe the design and implementation of such a robot.  We explicitly outline our design goals, and show how a capable robot can be assembled from off-the-shelf parts, for a modest cost, by a single person with only a few tools.  We also show how the robot can be used as a low-cost telepresence platform, giving the system a concrete purpose beyond being a low-cost development platform.

Gregory Hackmann, Minmin Chen, Octav Chipara, Chenyang Lu, Yixin Chen, Marin Kollef, Thomas C. Bailey

Clinical study has found early detection and intervention to be essential for preventing clinical deterioration in patients at general hospital units.  In this paper, we envision a two-tiered early warning system designed to identify the signs of clinical deterioration and provide early warning of serious clinical events.  The first tier of the system automatically identifies patients at risk of clinical deterioration from existing electronic medical record databases.  The second tier performs real-time clinical event detection based on real-time vital sign data collected from on-body wireless sensors attached to those high-risk patients.  We employ machine-learning techniques to analyze data from both tiers, assigning scores to patients in real time.  The assigned scores can then be used to trigger early-intervention alerts.  Preliminary study of an early warning system component and a wireless clinical monitoring system component demonstrate the feasibility of this two-tiered approach.

Manfred Georg

This dissertation addresses the problem of parameterizing object motion within a set of images taken with a stationary camera.  We develop data-driven methods across all image scales: characterizing motion observed at the scale of individual pixels, along extended structures such as roads, and whole image deformations such as lungs deforming over time.  The primary contributions include (a) fundamental studies of the relationship between spatio-temporal image derivatives accumulated at a pixel, and the object motions at that pixel, (b) data driven approaches to parameterize breath motion and reconstruct lung CT data volumes, and (c) defining and offering initial results for a new class of Partially Unsupervised Manifold Learning (PUML) problems, which often arise in medical imagery.

Specifically, we create energy functions for measuring how consistent a given velocity vector is with observed spatio-temporal image derivatives.  These energy functions are used to fit parametric snake models to roads using velocity constraints.  We create an automatic data-driven technique for finding the breath phase of lung CT scans which is able to replace external belt measurements currently in use clinically.  This approach is extended to automatically create a full deformation model of a CT lung volume during breathing or heart MRI during breathing and heartbeat.  Additionally, motivated by real use cases, we address a scenario in which a dataset is collected along with meta-data which describes some, but not all, aspects of the dataset.  We create an embedding which displays the remaining variability in a dataset after accounting for variability related to the meta-data.

Dissertation of Manfred Georg

Committee:
Robert Pless, Chair
Guy Genin
Cindy Grimm
Tao Ju
William Richard
John Shareshian

Huang-Ming Huang, Christopher Gill, Chengyang Lu

Modern computer architectures have evolved from uni-processor platforms to multi-processor and multi-core plat- forms, but traditional real-time distributed middleware such as RT-CORBA has not kept pace with that evolution.
To address those issues, this paper describes the design and implementation of MCFlow, a new real-time distributed middleware for dependent task graphs running on multi-core platforms. MCFlow provides the following contributions to the state of the art in real-time middleware: (1) it provides an efficient C++ based component model through which computations can be configured flexibly for execution within a single core, across cores of a common host, or spanning multiple hosts; (2) it allows optimizations for inter-component communication to avoid data copying without sacrificing the parallel executability of data dependent tasks; (3) it strictly separates timing and functional concerns of an application so that they can evolve and can be configured independently; and (4) it provides a novel event dispatching architecture that uses lock free algorithms to avoid mutex locking and reduce memory contention, CPU context switching, and priority inversion. We also present an empirical evaluation that demonstrates the efficacy of our approach.

Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis of the real-time flows that are scheduled using a fixed priority scheduling policy in a WirelessHART network. Simulations based on both random topologies and real network topologies of a physical testbed demonstrate the efficacy of our end-to-end delay analysis in terms of acceptance ratio under various fixed priority scheduling policies.

Charles Wiseman

Virtualized network infrastructures are currently deployed in both research and commercial contexts. The complexity of the virtualization layer varies greatly in different deployments, ranging from cloud computing environments, to carrier Ethernet applications using stacked VLANs, to networking testbeds.  In all of these cases, many users are sharing the resources of one provider and each user expects their resources to be isolated from all other users.  There are many challenges associated with the control and management of these systems, including resource allocation and sharing, resource isolation, system security, and usability.  Among the different types of virtualized infrastructures, network testbeds are of particular interest due to their widespread use in education and in the networking research community.

Networking researchers rely extensively on testbeds when evaluating new protocols and ideas.  Indeed, a substantial percentage of top research papers include results gathered from testbeds.  Network emulation testbeds in particular are often used to conduct innovative research because they allow users to emulate diverse network topologies in a controlled environment.  That is, researchers run experiments with a collection of resources that can be reconfigured to represent many different network scenarios.  The user typically has control over most of the resources in their experiment which results in a high level of reproducibility.  As such, these types of testbeds provide an excellent bridge between simulation and deployment of new ideas.  Unfortunately, most testbeds suffer from a general lack of resource extensibility and diversity.

This dissertation extends the current state of the art by designing a new, more general testbed infrastructure that expands and enhances the capabilities of modern testbeds.  This includes pertinent abstractions, software design, and related algorithms.  The design has also been prototyped in the form of the Open Network Laboratory network testbed, which has been successfully used in educational and research pursuits.  While the focus is on network testbeds, the results of this research will also be applicable to the broader class of virtualized system infrastructures.

Subharthi Paul, Raj Jain, Jianli Pan, Chakchai So-in

The next generation Internet needs to support multiple diverse application contexts. In this paper, we present Internet 3.0, a diversified, multi-tier architecture for the next generation Internet. Unlike the current Internet, Internet 3.0 defines a new set of primitives that allows diverse applications to compose and optimize their specific contexts over resources belonging to multiple ownerships. The key design philosophy is to enable diversity through explicit representation, negotiation and enforcement of policies at the granularity of network infrastructure, compute resources, data and users. The basis of the Internet 3.0 architecture is a generalized three-tier object model. The bottom tier consists of a high-speed network infrastructure. The second tier consists of compute resources or hosts. The third tier consists of data and users. The “tiered” organization of the entities in the object model depicts the natural dependency relationship between these entities in a communication context. All communication contexts, including the current Internet, may be represented as special cases within this generalized three-tier object model. The key contribution of this paper is a formal architectural representation of the Internet 3.0 architecture over the key primitive of the “Object Abstraction” and a detailed discussion of the various design aspects of the architecture, including the design of the “Context Router-” the key architectural element that powers an evolutionary deployment plan for the clean slate design ideas of Internet 3.0.

Qiang Lu and You Xu and Ruoyun Huang and Yixin Chen

Graph search has been employed by
many AI techniques and applications. A natural
way to improve the efficiency of search is to utilize ad-
vanced, more powerful computing platforms.  However, expensive computing infrastructures, such as supercomputers and large-scale
clusters, are traditionally available to only a limited
number of projects and researchers. As a results, most
AI applications, with access to only commodity com-
puters and clusters, cannot benefit from the efficiency
improvements of high-performance parallel search algorithms.
Cloud computing provides an attractive, highly
accessible alternative to other traditional high-
performance computing platforms. In this paper, we
first show that the run-time of our stochastic search algorithm in planning is a heavy-tailed distribution, which has a remarkable variability. Second, we propose an algorithm framework that
takes advantage of cloud computing.

Terry Tidwell, Robert Glaubius, Christopher D. Gill and William D. Smart

Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, optimal utility accrual scheduling design is needed for real-time cyber-physical domains.

In this paper we design optimal utility accrual scheduling policies for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process formulation of the scheduling problem. We use this formulation to demonstrate that our technique improves on existing heuristic utility accrual scheduling policies.

Simon Tam

Stroke is the leading cause of disability in the industrialized world. The disabilities caused by stroke can significantly impact the quality of daily life for stroke survivors. Studies show that a high number of daily body movement repetitions can help recover lost motor functionality. However, many stroke patients do not perform the home exercises needed to reach this high number of repetitions. Games for rehabilitation have been shown to provide motivation to perform home exercises. However, because stroke can leave survivors with different levels of disability, custom games are required. Creating custom games, though, is time consuming and requires advanced programming knowledge. A tool for quick and easy game development is a solution to this problem. In this master’s project, I collaborated with a doctoral occupational therapy student to take steps towards developing a game authoring environment custom to therapists.

Jwalant Ahir; Jeremy Buhler; Roger D. Chamberlain

Biosequence similarity search is an important application in computational biology. Mercury BLASTN, an FPGA-based implementation of BLAST for DNA, is one of the alternatives for fast DNA sequence comparison. The re-design of BLAST into a streaming application combined with a high-throughput hardware pipeline have enabled Mercury BLAST to emerge as one of the fastest implementations of bio-sequence similarity search. This performance can be further enhanced by exploiting the data-level parallelism present within the application. Here we present a multiple FPGA-based Mercury BLASTN design in order to double the speed and throughput of DNA sequence computation. This paper describes a dual Mercury BLASTN design, the detailed design of the split and merge functions, and simulation results.

Nathan Jacobs

The web has an enormous collection of live cameras that capture images of roads, beaches, cities, mountains, buildings, and forests.  With an appropriate foundation, this massively distributed, scalable, and already existing network of cameras could be used as a new global sensor.  The sheer number of cameras and their broad spatial distribution prompts new questions in computer vision: How can you automatically geo-locate each camera? How can you learn the 3D structure of the scene? How can you correct the color measurements from the camera? What environmental properties can you extract?

We address these questions using models of the geometry and statistics of natural outdoor scenes, and with an understanding of how image appearance varies due to transient objects, the weather, the time of day, and the season. We show algorithms to calibrate cameras and annotate scenes that formalize this understanding in classical linear and nonlinear optimization frameworks.  Our work uses images captured at long temporal scales, ranging from minutes to years; often these images are from a database of images we created by capturing  images from 1000 webcams every half hour.  By exploring natural cues capable of working over such long time scales on a broad range of scenes, we deepen our understanding of the interplay between geographic location, time, and the causes of image appearance change.

William D. Smart, Annamaria Pileggi, and Leila Takayama

This is a collection of papers presented at the workshop "What Do Collaborations with the Arts Have to Say About HRI", held at the 2010 Human-Robot Interaction Conference, in Osaka, Japan.

Manfred Georg, Tobias Preusser, and Horst K. Hahn

We present a framework for the construction of vascular systems based on optimality principles of theoretical physiology.  Given the position and flow distribution of end points of a vascular system, we construct the topology and positions of internal nodes to complete the vascular system in a realistic manner.  Optimization is driven by intravascular volume minimization with constraints derived from physiological principles.  Direct optimization of a vascular system, including topological changes, is used instead of simulating vessel growth.  A good initial topology is found by extracting key information from a previously optimized model with less detail.  This technique is used iteratively in a multi-level approach to create a globally optimized vascular system.

Most of this work was completed at Fraunhofer MeVis during the summer of 2004.

Emily M. Yang

Persons who have suffered from stroke participate in occupational therapy to help recover occupational functionality, but therapy is expensive and maximal recovery often depends on repetitive, tedious exercises to be done by patients both in therapy sessions and on their own. Often patients do not have the resources or motivation to complete the treatment required to give them the best results. This thesis is presented as part of a larger project in which we aim to enable occupational therapists to use the Looking Glass programming environment to create computer games for their patients that can be played inexpensively and effectively, both inside and outside of therapy sessions. Looking Glass will allow for occupational therapists with little or no programming background to write customized games for their patients. Through using Wii remotes and webcams to track movement and translate it to a computer game, this solution has the potential to provide a more engaging and interesting way for patients to correct ly do repetitive movements without needing constant therapist supervision or expensive and complicated equipment. It also can provide highly customizable and adjustable game settings to accommodate for the wide range of impairments that can result from stroke. This thesis presents a study of the needs of occupational therapists and stroke patients who compose the user base of the project and implications for the design, the development of a webcam color tracking system to be used for movement tracking in games, and an application to be used by therapists to assign specific, patient-tailored calibrations and game levels as part of treatments and to track and organize improvement statistics. These are all key components required for the successful development of the overall project.

You Xu

Partial Order Reduction (POR) is a technique that reduces the search space by recognizing interchangeable orders between actions and expanding only a subset of all possible orders during the search. It has been extensively studied in model checking and has proven to be an enabling technique for reducing the search space and costs.

Several POR algorithms have been proposed in planning, including the Expansion Core (EC) and Stratified Planning (SP) algorithms. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods.

In this thesis, we have proposed a unifying theory that provides a necessary and sufficient condition for two actions to be semi-commutative. We have also revealed that semi-commutativity is the central property that enables POR. We have also interpreted both EC and SP algorithms using this new theory. Further, we have proposed new, stronger POR algorithms based on the new theory. We have also applied these new algorithms to solve benchmark problems across various planning domains. Experimental results have shown significant search cost reduction.