Matching Items (44)
Description
This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram. A counterpart for the grid-based model is provided; it creates all edges deterministically and shows an asymptotically matching upper bound on the route length. The main goal is to improve greedy routing through a decentralized machine learning process. Two considered methods are based on weighted majority and an algorithm of de Farias and Megiddo, both learning from feedback using ensembles of experts. Tests are run on both artificial and real networks, with decentralized spectral graph embedding supplying geometric information for real networks where it is not intrinsically available. An important measure analyzed in this work is overpayment, the difference between the cost of the method and that of the shortest path. Adaptive routing overtakes greedy after about a hundred or fewer searches per node, consistently across different network sizes and types. Learning stabilizes, typically at overpayment of a third to a half of that by greedy. The problem is made more difficult by eliminating the knowledge of neighbors' locations or by introducing uncooperative nodes. Even under these conditions, the learned routes are usually better than the greedy routes. The second part of the dissertation is related to the community structure of unannotated networks. A modularity-based algorithm of Newman is extended to work with overlapping communities (including considerably overlapping communities), where each node locally makes decisions to which potential communities it belongs. To measure quality of a cover of overlapping communities, a notion of a node contribution to modularity is introduced, and subsequently the notion of modularity is extended from partitions to covers. The final part considers a problem of network anonymization, mostly by the means of edge deletion. The point of interest is utility preservation. It is shown that a concentration on the preservation of routing abilities might damage the preservation of community structure, and vice versa.
ContributorsBakun, Oleg (Author) / Konjevod, Goran (Thesis advisor) / Richa, Andrea (Thesis advisor) / Syrotiuk, Violet R. (Committee member) / Czygrinow, Andrzej (Committee member) / Arizona State University (Publisher)
Created2011
Description
Finding the optimal solution to a problem with an enormous search space can be challenging. Unless a combinatorial construction technique is found that also guarantees the optimality of the resulting solution, this could be an infeasible task. If such a technique is unavailable, different heuristic methods are generally used to improve the upper bound on the size of the optimal solution. This dissertation presents an alternative method which can be used to improve a solution to a problem rather than construct a solution from scratch. Necessity analysis, which is the key to this approach, is the process of analyzing the necessity of each element in a solution. The post-optimization algorithm presented here utilizes the result of the necessity analysis to improve the quality of the solution by eliminating unnecessary objects from the solution. While this technique could potentially be applied to different domains, this dissertation focuses on k-restriction problems, where a solution to the problem can be presented as an array. A scalable post-optimization algorithm for covering arrays is described, which starts from a valid solution and performs necessity analysis to iteratively improve the quality of the solution. It is shown that not only can this technique improve upon the previously best known results, it can also be added as a refinement step to any construction technique and in most cases further improvements are expected. The post-optimization algorithm is then modified to accommodate every k-restriction problem; and this generic algorithm can be used as a starting point to create a reasonable sized solution for any such problem. This generic algorithm is then further refined for hash family problems, by adding a conflict graph analysis to the necessity analysis phase. By recoloring the conflict graphs a new degree of flexibility is explored, which can further improve the quality of the solution.
ContributorsNayeri, Peyman (Author) / Colbourn, Charles (Thesis advisor) / Konjevod, Goran (Thesis advisor) / Sen, Arunabha (Committee member) / Stanzione Jr, Daniel (Committee member) / Arizona State University (Publisher)
Created2011
Description
Reverse engineering gene regulatory networks (GRNs) is an important problem in the domain of Systems Biology. Learning GRNs is challenging due to the inherent complexity of the real regulatory networks and the heterogeneity of samples in available biomedical data. Real world biological data are commonly collected from broad surveys (profiling studies) and aggregate highly heterogeneous biological samples. Popular methods to learn GRNs simplistically assume a single universal regulatory network corresponding to available data. They neglect regulatory network adaptation due to change in underlying conditions and cellular phenotype or both. This dissertation presents a novel computational framework to learn common regulatory interactions and networks underlying the different sets of relatively homogeneous samples from real world biological data. The characteristic set of samples/conditions and corresponding regulatory interactions defines the cellular context (context). Context, in this dissertation, represents the deterministic transcriptional activity within the specific cellular regulatory mechanism. The major contributions of this framework include - modeling and learning context specific GRNs; associating enriched samples with contexts to interpret contextual interactions using biological knowledge; pruning extraneous edges from the context-specific GRN to improve the precision of the final GRNs; integrating multisource data to learn inter and intra domain interactions and increase confidence in obtained GRNs; and finally, learning combinatorial conditioning factors from the data to identify regulatory cofactors. The framework, Expattern, was applied to both real world and synthetic data. Interesting insights were obtained into mechanism of action of drugs on analysis of NCI60 drug activity and gene expression data. Application to refractory cancer data and Glioblastoma multiforme yield GRNs that were readily annotated with context-specific phenotypic information. Refractory cancer GRNs also displayed associations between distinct cancers, not observed through only clustering. Performance comparisons on multi-context synthetic data show the framework Expattern performs better than other comparable methods.
ContributorsSen, Ina (Author) / Kim, Seungchan (Thesis advisor) / Baral, Chitta (Committee member) / Bittner, Michael (Committee member) / Konjevod, Goran (Committee member) / Arizona State University (Publisher)
Created2011
Description
Demand for biosensor research applications is growing steadily. According to a new report by Frost & Sullivan, the biosensor market is expected to reach $14.42 billion by 2016. Clinical diagnostic applications continue to be the largest market for biosensors, and this demand is likely to continue through 2016 and beyond. Biosensor technology for use in clinical diagnostics, however, requires translational research that moves bench science and theoretical knowledge toward marketable products. Despite the high volume of academic research to date, only a handful of biomedical devices have become viable commercial applications. Academic research must increase its focus on practical uses for biosensors. This dissertation is an example of this increased focus, and discusses work to advance microfluidic-based protein biosensor technologies for practical use in clinical diagnostics. Four areas of work are discussed: The first involved work to develop reusable/reconfigurable biosensors that are useful in applications like biochemical science and analytical chemistry that require detailed sensor calibration. This work resulted in a prototype sensor and an in-situ electrochemical surface regeneration technique that can be used to produce microfluidic-based reusable biosensors. The second area of work looked at non-specific adsorption (NSA) of biomolecules, which is a persistent challenge in conventional microfluidic biosensors. The results of this work produced design methods that reduce the NSA. The third area of work involved a novel microfluidic sensing platform that was designed to detect target biomarkers using competitive protein adsorption. This technique uses physical adsorption of proteins to a surface rather than complex and time-consuming immobilization procedures. This method enabled us to selectively detect a thyroid cancer biomarker, thyroglobulin, in a controlled-proteins cocktail and a cardiovascular biomarker, fibrinogen, in undiluted human serum. The fourth area of work involved expanding the technique to produce a unique protein identification method; Pattern-recognition. A sample mixture of proteins generates a distinctive composite pattern upon interaction with a sensing platform consisting of multiple surfaces whereby each surface consists of a distinct type of protein pre-adsorbed on the surface. The utility of the "pattern-recognition" sensing mechanism was then verified via recognition of a particular biomarker, C-reactive protein, in the cocktail sample mixture.
ContributorsChoi, Seokheun (Author) / Chae, Junseok (Thesis advisor) / Tao, Nongjian (Committee member) / Yu, Hongyu (Committee member) / Forzani, Erica (Committee member) / Arizona State University (Publisher)
Created2011
Description
The past two decades have been monumental in the advancement of microchips designed for a diverse range of medical applications and bio-analysis. Owing to the remarkable progress in micro-fabrication technology, complex chemical and electro-mechanical features can now be integrated into chip-scale devices for use in biosensing and physiological measurements. Some of these devices have made enormous contributions in the study of complex biochemical processes occurring at the molecular and cellular levels while others overcame the challenges of replicating various functions of human organs as implant systems. This thesis presents test data and analysis of two such systems. First, an ISFET based pH sensor is characterized for its performance in a continuous pH monitoring application. Many of the basic properties of ISFETs including I-V characteristics, pH sensitivity and more importantly, its long term drift behavior have been investigated. A new theory based on frequent switching of electric field across the gate oxide to decrease the rate of current drift has been successfully implemented with the help of an automated data acquisition and switching system. The system was further tested for a range of duty cycles in order to accurately determine the minimum length of time required to fully reset the drift. Second, a microfluidic based vestibular implant system was tested for its underlying characteristics as a light sensor. A computer controlled tilt platform was then implemented to further test its sensitivity to inclinations and thus it‟s more important role as a tilt sensor. The sensor operates through means of optoelectronics and relies on the signals generated from photodiode arrays as a result of light being incident on them. ISFET results show a significant drop in the overall drift and good linear characteristics. The drift was seen to reset at less than an hour. The photodiodes show ideal I-V comparison between photoconductive and photovoltaic modes of operation with maximum responsivity at 400nm and a shunt resistance of 394 MΩ. Additionally, post-processing of the tilt sensor to incorporate the sensing fluids is outlined. Based on several test and fabrication results, a possible method of sealing the open cavity of the chip using a UV curable epoxy has been discussed.
ContributorsMamun, Samiha (Author) / Christen, Jennifer Blain (Thesis advisor) / Goryll, Michael (Committee member) / Yu, Hongyu (Committee member) / Arizona State University (Publisher)
Created2011
Description
During the last decades the development of the transistor and its continuous down-scaling allowed the appearance of cost effective wireless communication systems. New generation wideband wireless mobile systems demand high linearity, low power consumption and the low cost devices. Traditional RF systems are mainly analog-based circuitry. Contrary to digital circuits, the technology scaling results in reduction on the maximum voltage swing which makes RF design very challenging. Pushing the interface between the digital and analog boundary of the RF systems closer to the antenna becomes an attractive trend for modern RF devices. In order to take full advantages of the deep submicron CMOS technologies and digital signal processing (DSP), there is a strong trend towards the development of digital transmitter where the RF upconversion is part of the digital-to-analog conversion (DAC). This thesis presents a new digital intermediate frequency (IF) to RF transmitter for 2GHz wideband code division multiple access (W-CDMA). The proposed transmitter integrates a 3-level digital IF current-steering cell, an up-conversion mixer with a tuned load and an RF variable gain amplifier (RF VGA) with an embedded finite impulse response (FIR) reconstruction filter in the up-conversion path. A 4th-order 1.5-bit IF bandpass sigma delta modulator (BP SDM) is designed to support in-band SNR while the out-of-band quantization noise due to the noise shaping is suppressed by the embedded reconstruction filter to meet spectrum emission mask and ACPR requirements. The RF VGA provides 50dB power scaling in 10-dB steps with less than 1dB gain error. The design is fabricated in a 0.18um CMOS technology with a total core area of 0.8 x 1.6 mm2. The IC delivers 0dBm output power at 2GHz and it draws approximately 120mA from a 1.8V DC supply at the maximum output power. The measurement results proved that a digital-intensive digital IF to RF converter architecture can be successfully employed for WCDMA transmitter application.
ContributorsHan, Yongping (Author) / Kiaei, Sayfe (Thesis advisor) / Yu, Hongyu (Committee member) / Bakkaloglu, Bertan (Committee member) / Aberle, James T., 1961- (Committee member) / Barnaby, Hugh (Committee member) / Arizona State University (Publisher)
Created2012
Description
Advances in miniaturized sensors and wireless technologies have enabled mobile health systems for efficient healthcare. A mobile health system assists the physician to monitor the patient's progress remotely and provide quick feedbacks and suggestions in case of emergencies, which reduces the cost of healthcare without the expense of hospitalization. This work involves development of an innovative mobile health system with adaptive biofeedback mechanism and demonstrates the importance of biofeedback in accurate measurements of physiological parameters to facilitate the diagnosis in mobile health systems. Resting Metabolic Rate (RMR) assessment, a key aspect in the treatment of diet related health problems is considered as a model to demonstrate the importance of adaptive biofeedback in mobile health. A breathing biofeedback mechanism has been implemented with digital signal processing techniques for real-time visual and musical guidance to accurately measure the RMR. The effects of adaptive biofeedback with musical and visual guidance were assessed on 22 healthy subjects (12 men, 10 women). Eight RMR measurements were taken for each subject on different days under same conditions. It was observed the subjects unconsciously followed breathing biofeedback, yielding consistent and accurate measurements for the diagnosis. The coefficient of variation of the measured metabolic parameters decreased significantly (p < 0.05) for 20 subjects out of 22 subjects.
ContributorsKrishnan, Ranganath (Author) / Tao, Nongjian (Thesis advisor) / Forzani, Erica (Committee member) / Yu, Hongyu (Committee member) / Arizona State University (Publisher)
Created2012
Description
In this thesis, an approach to develop low-frequency accelerometer based on molecular electronic transducers (MET) in an electrochemical cell is presented. Molecular electronic transducers are a class of inertial sensors which are based on an electrochemical mechanism. Motion sensors based on MET technology consist of an electrochemical cell that can be used to detect the movement of liquid electrolyte between electrodes by converting it to an output current. Seismometers based on MET technology are attractive for planetary applications due to their high sensitivity, low noise, small size and independence on the direction of sensitivity axis. In addition, the fact that MET based sensors have a liquid inertial mass with no moving parts makes them rugged and shock tolerant (basic survivability has been demonstrated to >20 kG).
A Zn-Cu electrochemical cell (Galvanic cell) was applied in the low-frequency accelerometer. Experimental results show that external vibrations (range from 18 to 70 Hz) were successfully detected by this accelerometer as reactions Zn→〖Zn〗^(2+)+2e^- occurs around the anode and 〖Cu〗^(2+)+2e^-→Cu around the cathode. Accordingly, the sensitivity of this MET device design is to achieve 10.4 V/G at 18 Hz. And the sources of noise have been analyzed.
A Zn-Cu electrochemical cell (Galvanic cell) was applied in the low-frequency accelerometer. Experimental results show that external vibrations (range from 18 to 70 Hz) were successfully detected by this accelerometer as reactions Zn→〖Zn〗^(2+)+2e^- occurs around the anode and 〖Cu〗^(2+)+2e^-→Cu around the cathode. Accordingly, the sensitivity of this MET device design is to achieve 10.4 V/G at 18 Hz. And the sources of noise have been analyzed.
ContributorsZhao, Zuofeng (Author) / Yu, Hongyu (Thesis advisor) / Zhang, Junshan (Committee member) / Jiang, Hanqing (Committee member) / Arizona State University (Publisher)
Created2015
Description
Energy harvesting from ambient is important to configuring Wireless Sensor Networks (WSN) for environmental data collecting. In this work, highly flexible thermoelectric generators (TEGs) have been studied and fabricated to supply power to the wireless sensor notes used for data collecting in hot spring environment. The fabricated flexible TEGs can be easily deployed on the uneven surface of heated rocks at the rim of hot springs. By employing the temperature gradient between the hot rock surface and the air, these TEGs can generate power to extend the battery lifetime of the sensor notes and therefore reduce multiple batteries changes where the environment is usually harsh in hot springs. Also, they show great promise for self-powered wireless sensor notes. Traditional thermoelectric material bismuth telluride (Bi2Te3) and advanced MEMS (Microelectromechanical systems) thin film techniques were used for the fabrication. Test results show that when a flexible TEG array with an area of 3.4cm2 was placed on the hot plate surface of 80°C in the air under room temperature, it had an open circuit voltage output of 17.6mV and a short circuit current output of 0.53mA. The generated power was approximately 7mW/m2.
On the other hand, high pressure, temperatures that can reach boiling, and the pH of different hot springs ranging from <2 to >9 make hot spring ecosystem a unique environment that is difficult to study. WSN allows many scientific studies in harsh environments that are not feasible with traditional instrumentation. However, wireless pH sensing for long time in situ data collection is still challenging for two reasons. First, the existing commercial-off-the-shelf pH meters are frequent calibration dependent; second, biofouling causes significant measurement error and drift. In this work, 2-dimentional graphene pH sensors were studied and calibration free graphene pH sensor prototypes were fabricated. Test result shows the resistance of the fabricated device changes linearly with the pH values (in the range of 3-11) in the surrounding liquid environment. Field tests show graphene layer greatly prevented the microbial fouling. Therefore, graphene pH sensors are promising candidates that can be effectively used for wireless pH sensing in exploration of hot spring ecosystems.
On the other hand, high pressure, temperatures that can reach boiling, and the pH of different hot springs ranging from <2 to >9 make hot spring ecosystem a unique environment that is difficult to study. WSN allows many scientific studies in harsh environments that are not feasible with traditional instrumentation. However, wireless pH sensing for long time in situ data collection is still challenging for two reasons. First, the existing commercial-off-the-shelf pH meters are frequent calibration dependent; second, biofouling causes significant measurement error and drift. In this work, 2-dimentional graphene pH sensors were studied and calibration free graphene pH sensor prototypes were fabricated. Test result shows the resistance of the fabricated device changes linearly with the pH values (in the range of 3-11) in the surrounding liquid environment. Field tests show graphene layer greatly prevented the microbial fouling. Therefore, graphene pH sensors are promising candidates that can be effectively used for wireless pH sensing in exploration of hot spring ecosystems.
ContributorsHan, Ruirui (Author) / Yu, Hongyu (Thesis advisor) / Jiang, Hanqing (Committee member) / Yu, Hongbin (Committee member) / Garnero, Edward (Committee member) / Li, Mingming (Committee member) / Arizona State University (Publisher)
Created2018
Description
The recent emergence of DNA-based diagnostics increases the demand for rapid DNA sequencing technologies. One method to achieve this is to pass DNA through a nanopore, recording the trans-membrane current with a low-noise current amplifier. The project outlined in this report aims to demonstrate a design of a custom amplifier that offers a wider bandwidth than current designs while maintaining a low signal to noise ratio. The novel amplifier has been designed such that a multi-stage RF signal chain is integrated with an existing amplifier circuit to achieve DNA translocation. Both the existing amplifier circuit and the RF signal chain have produced outputs showing that the two amplifiers are functional and both low frequency signals and high frequency signals can be amplified with this comprehensive circuit design.
ContributorsDharan, Abhishek (Co-author) / Becker, Jared (Co-author) / Goryll, Michael (Thesis director) / Yu, Hongyu (Committee member) / Barrett, The Honors College (Contributor) / Electrical Engineering Program (Contributor)
Created2014-05