Search

Distributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme.

A generic wafer-level packaging technology for high-performance MEMS devices, operating under harsh external conditions is developed. This technology not only provides physical protection from the surroundings, but also provides thermal and mechanical isolation to enhance device performance. The wafer-level encapsulation and generic assembly approach accommodate a wide range of MEMS devices with minimal process lead-time and manufacturing cost. To realize this environment-resistant package, thermal isolation, mechanical isolation, generic device transfer/integration, wafer-level vacuum packaging, and feedthroughs have been developed. The environment-resistant package consists of two substrates: a platform substrate providing thermal and mechanical isolation, and a package cap wafer providing vacuum encapsulation. Thermal stabilization is provided by oven-controlling the device at a temperature higher than the maximum environment temperature utilizing a heater and a temperature sensor located on the platform or the MEMS device. The heated structure is thermally isolated from the environment by isolation suspensions, anti-radiation shield, and vacuum encapsulation to minimize heat loss. The isolation suspensions are designed with high thermal resistance for minimal heat loss, sufficient stiffness for mechanical support, and flexibility for rejecting environmental vibrations. The package cap seals the MEMS device in vacuum. Vertical feedthroughs for a signal delivery are formed on the platform substrate or the cap wafer. These vertical feedthroughs save area and allow direct attachment to circuit boards. Shock absorption layers, and a getter layer for achieving and maintaining high vacuum are deposited on the inside wall of the package. Performance is evaluated by packaging Pirani gauges and mode-matched tuning fork gyroscopes. The package size is 1.2×1.2×0.17mm3, and the packaged device size is 4.5×4.5×0.5mm3. The package has maintained vacuum pressure of ~6 mTorr for ~1 year. A packaged gyroscope shows a high-Q mode-matched operation (Q~65,000) at a constant temperature of −5°C. Allan variance analysis displays an estimated angle random walk (ARW) of 0.012°/√hr and a bias instability value of 0.55°/hr at a constant −5°C. Drive frequency stability of 0.22ppm/°C is obtained using a compensated oven-control approach. Low power consumption of 33mW for oven-control at 80°C is demonstrated when the environment temperature is −30°C. The temperature control accuracy is ± 0.2°C.