Data dissemination among wireless devices is an essential application in wireless networks. In contrast to its wired counterparts which have more stable network settings, wireless networks are subject to network dynamics, such as variable network topology, channel availability and capacity, which are due to user mobility, signal collision, random channel fading and scattering, etc. Network dynamics complicate the protocol design for optimal data disseminations. Although the topic has been intensively discussed for many years, existing solutions are still not completely satisfactory, especially for stochastic or arbitrary networks. In this thesis, we address optimal data dissemination in both stochastic and arbitrary wireless networks, using techniques of Lyapunov optimization, graph theory, network coding, multi-resolution coding and successive interference cancellation. We first discuss the maximization of time-averaged throughput utility over a long run for unicast and multirate multicast, respectively, in stochastic wireless networks without probing into the future. For multi-session unicast communications, a utility-maximizing cross-layer design, composed of joint end-to-end rate control, routing, and channel allocation, is proposed for cognitive radio networks with stochastic primary user occupations. Then, we study optimal multirate multicast to receivers with non-uniform receiving rates, also making dynamic cross-layer decisions, in a general wireless network with both a timevarying topology and random channel capacities, by utilizing random linear network coding and multi-resolution coding. In both solutions, we assume users are selfish and prefer only to relay data for others with strong social ties. Such social selfishness of users is a new constraint in network protocol design. Its impact on efficient data dissemination in wireless networks is largely unstudied, especially under stochastic settings. Lyapunov optimization is applied in our protocol design achieving close-to-optimal utilities. Next, we turn to latency-minimizing data aggregation in wireless sensor networks having arbitrary network topologies under the physical interference model. Different from our effort for stochastic networks where we target at time-averaged optimality over a long run, the objective here is to minimize the time-span to accomplish one round of aggregation scheduling for all sensors in an arbitrary topology. This problem is NP-hard, involving both aggregation tree construction and collision-free link scheduling. The current literature mostly considers the protocol interference model, which has been shown to be less practical than the physical interference model in characterizing the interference relations in the real world. A distributed solution under the physical interference model is challenging since cumulative interferences from all concurrently transmitting devices need to be well measured. In this thesis, we present a distributed aggregation protocol with an improved approximation ratio as compared with previous work. We then discuss the tradeoff between aggregation latency and energy consumption for arbitrary topologies when the successive interference cancellation technique is in force. Another distributed algorithm is introduced with asymptotic optimality in both aggregation latency and latency-energy tradeoff. Through theoretical analysis and empirical study, we rigorously examine the optimality of our protocols comparing with both the theoretical optima and existing solutions. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

We consider three problems in this dissertation, all under the unifying theme of random matrix products. The first and second problems are concerned with weak convergence in stochastic matrices and circulant matrices, respectively, and the third is concerned with the numerical calculation of the Lyapunov exponent associated with some random Fibonacci sequences. Stochastic matrices are nonnegative matrices whose row sums are all equal to 1. They are most commonly encountered as transition matrices of Markov chains. Circulant matrices, on the other hand, are matrices where each row after the first is just the previous row cyclically shifted to the right by one position. Like stochastic matrices, circulant matrices are ubiquitous in the literature.In the first problem, we study the weak convergence of the convolution sequence mu to the n, where mu is a probability measure with support S sub mu inside the space S of d by d stochastic matrices, d greater than or equal to 3. Note that mu to the n is precisely the distribution of the product X sub 1 times X sub 2 times and so on times X sub n of the mu distributed independent random variables X sub 1, X sub 2, and so on, X sub n taking values in S. In [CR] Santanu Chakraborty and B.V. Rao introduced a cyclicity condition on S sub mu and showed that this condition is necessary and sufficient for mu to the n to not converge weakly when d is equal to 3 and the minimal rank r of the matrices in the closed semigroup S generated by S sub mu is 2. Here, we extend this result to any d bigger than 3. Moreover, we show that when the minimal rank r is not 2, this result does not always hold.The second problem is an investigation of weak convergence in another direction, namely the case when the probability measure mu's support S sub mu consists of d by d circulant matrices, d greater than or equal to 3, which are not necessarily nonnegative. The resulting semigroup S generated by S sub mu now lacking the nice property of compactness in the case of stochastic matrices, we assume tightness of the sequence mu to the n to analyze the problem. Our approach is based on the work of Mukherjea and his collaborators, who in [LM] and [DM] presented a method based on a bookkeeping of the possible structure of the compact kernel K of S.The third problem considered in this dissertation is the numerical determination of Lyapunov exponents of some random Fibonacci sequences, which are stochastic versions of the classical Fibonacci sequence f sub (n plus 1) equals f sub n plus f sub (n minus 1), n greater than or equal to 1, and f sub 0 equal f sub 1 equals 1, obtained by randomizing one or both signs on the right side of the defining equation and or adding a "growth parameter." These sequences may be viewed as coming from a sequence of products of i.i.d. random matrices and their rate of growth measured by the associated Lyapunov exponent. Following techniques presented by Embree and Trefethen in their numerical paper [ET], we study the behavior of the Lyapunov exponents as a function of the probability p of choosing plus in the sign randomization.

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

Model reduction is a common theme within the simulation, control and optimization of complex dynamical systems. For instance, in control problems for partial differential equations, the associated large-scale systems have to be solved very often. To attack these problems in reasonable time it is absolutely necessary to reduce the dimension of the underlying system. We focus on model reduction by balanced truncation where a system theoretical background provides some desirable properties of the reduced-order system. The major computational task in balanced truncation is the solution of large-scale Lyapunov equations, thus the method is of limited use for really large-scale applications. We develop an effective implementation of balancing-related model reduction methods in exploiting the structure of the underlying problem. This is done by a data-sparse approximation of the large-scale state matrix A using the hierarchical matrix format. Furthermore, we integrate the corresponding formatted arithmetic in the sign function method for computing approximate solution factors of the Lyapunov equations. This approach is well-suited for a class of practical relevant problems and allows the application of balanced truncation and related methods to systems coming from 2D and 3D FEM and BEM discretizations.

No description available.

Formal methods is a discipline of using a collection of mathematical techniques and formalisms to model and analyze software systems. Motivated by the new formal methods-based certification recommendations for safety-critical embedded software and the significant increase in the cost of verification and validation (V\&V), this research is about creating a software development process for control systems that can provide mathematical guarantees of high-level functional properties on the code. The process, dubbed credible autocoding, leverages control theory in the automatic generation of control software documented with proofs of their stability and performance. The main output of this research is an automated, credible autocoding prototype that transforms the Simulink model of the controller into C code documented with a code-level proof of the stability of the controller. The code-level proof, expressed using a formal specification language, are embedded into the code as annotations. The annotations guarantee that the auto-generated code conforms to the input model to the extent that key properties are satisfied. They also provide sufficient information to enable an independent, automatic, formal verification of the auto-generated controller software.

We investigate how the formation of heterogeneity and structures in flows through explicit porous microstructures depends upon the geometric and topological observables of the porous medium. Using direct numerical simulations of single-phase, isothermal, laminar fluid flow through realistic three-dimensional stochastically generated pore structures, hereafter referred to as pore spaces, the characteristics of the resulting steady state velocity fields are related to physical characteristics of the pore spaces. The results suggest that the spatially variable resistance offered by the geometry and topology of the pore space induces a highly heterogeneous fluid velocity field therein. Focus is placed on three different length scales: macroscopic (cm), mesoscopic (mm), and microscopic (microns). At the macroscopic length scale, volume averaging is used to relate porosity, mean hydraulic radius, and their product to the permeability of the pore space. At the mesoscopic scale, the effect of a medium's porosity on fluid particle trajectory attributes, such as passage time and tortuosity, is studied. At the final length scale, that of the microscopic in-pore fluid dynamics, finite time Lyapunov exponents are used to determine expanding, contracting, and hyperbolic regions in the flow field, which are then related to the local structure of the pore space. The results have implications to contaminant transport, mixing, and how chemical reactions are induced at the pore-scale. A description of the adopted numerical methods to simulate flow and generate the pore space are provided as well.

This dissertation investigates advanced concepts in terminal missile guidance. The terminal phase of missile guidance usually lasts less than ten seconds and calls for very accurate maneuvering to ensure intercept. Technological advancements have produced increasingly sophisticated threats that greatly reduce the effectiveness of traditional approaches to missile guidance. Because of this, terminal missile guidance is, and will remain, an important and active area of research. The complexity of the problem and the desire for an optimal solution has resulted in researchers focusing on simplistic, usually linear, models. The fruit of these endeavors has resulted in some of the world's most advanced weapons systems. Even so, the resulting guidance schemes cannot possibly counter the evolving threats that will push the system outside the linear envelope for which they were designed. The research done in this dissertation greatly extends previous research in the area of optimal missile guidance. Herein it is shown that optimal missile guidance is fundamentally a pairing of an optimal guidance strategy and an optimal control strategy. The optimal guidance strategy is determined from a missile's information constraints, which are themselves largely determined from the missile's sensors. The optimal control strategy is determined by the missile's control constraints, and works to achieve a specified guidance strategy. This dichotomy of missile guidance is demonstrated by showing that missiles having different control constraints utilize the same guidance strategy so long as the information constraints are the same. This concept has hitherto been unrecognized because of the difficulty in developing an optimal control for the nonlinear set of equations that result from control constraints. Having overcome this difficulty by indirect means, evidence of the guidance strategy paradigm emerged. The guidance strategy paradigm is used to develop two advanced guidance laws. The new guidance laws are compared qualitatively and quantitatively with existing guidance laws.

Presently power systems are being operated under high stress level conditions unforeseen at the moment they were designed. These operating conditions have negatively impacted reliability, controllability and security margins. FACTS devices and HVDC transmissions have emerged as solutions to help power systems to increase the stability margins. VSC-HVDC transmissions are of particular interest since the principal characteristic of this type of transmission is its ability to independently control active power and reactive power. This thesis presents various control strategies to improve damping of electromechanical oscillations, and also enhance transient and voltage stability by using VSC-HVDC transmissions. These control strategies are based of different theory frames, namely, modal analysis, nonlinear control (Lyapunov theory) and model predictive control. In the derivation of the control strategies two models of VSC-HVDC transmissions were also derived. They are Injection Model and Simple Model. Simulations done in the HVDC Light Open Model showed the validity of the derived models of VSC-HVDC transmissions and the effectiveness of the control strategies. Furthermore the thesis presents an analysis of local and remote information used as inputs signals in the control strategies. It also describes an approach to relate modal analysis and the SIME method. This approach allowed the application of SIME method with a reduced number of generators, which were selected based on modal analysis. As a general conclusion it was shown that VSC-HVDC transmissions with an appropriate input signal and control strategy was an effective means to improve the system stability. / QC 20110412

An analog controller has been analyzed and built for an electrostatic micro-cantilever beam. The closed loop MEMS device can be used as both actuator and sensor. As an actuator it will have the advantage of large stable travel range up to 90% of the gap. As a sensor the beam is to be driven into chaotic motion which is very sensitive changes in the system parameters. Two versions of the controller have been analyzed and implemented, one for the actuator and one for the sensor. For the actuator, preliminary experiments show good matching with the model. As for the sensor, the dynamic behavior have been studied and the best operating regions have been determined.