Synthesizing Robust Networks for Engineering Applications with Resource Constraints

This dissertation deals with the following simpler version of an open problem in system realization theory which has several important engineering applications: Given a collection of masses and a set of linear springs with a specified cost and stiffness, a resource constraint in terms of a budget on the total cost, the problem is to determine an optimal connection of masses and springs so that the resulting structure is as stiff as possible, i.e., the structure is connected and its smallest nonzero natural frequency is as large as possible.

One often encounters variants of this problem in deploying Unmanned Aerial Vehicles (UAVs) for civilian and military applications. In such problems, one must determine the pairs of UAVs that must maintain a communication link so that constraints on resources and performance, such as a limit on the maximum number of communication links deployed, power consumed and maximum latency in routing information from one UAV to the other, are met and a performance objective is maximized. In this dissertation, algebraic connectivity, or its mechanical analog - the smallest non-zero natural frequency of a connected structure was chosen as a performance objective. Algebraic connectivity determines the convergence rate of consensus protocols and error attenuation in UAV formations and is chosen to be a performance objective as it can be viewed as a measure of robustness in UAV communication networks to random node failures.

Underlying the mechanical and UAV network synthesis problems is a Mixed Integer Semi-Definite Program (MISDP), which was recently shown to be a NP-hard problem. There has not been any systematic procedure in the literature to solve this problem. This dissertation is aimed at addressing this void in the literature. The novel contributions of this dissertation to the literature are as follows: a) An iterative primal-dual algorithm and an algorithm based on the outer approximation of the semi-definite constraint utilizing a cutting plane technique were developed for computing optimal algebraic connectivity. These algorithms are based on a polyhedral approximation of the feasible set of MISDP, b) A bisection algorithm was developed to reduce the MISDP to a Binary Semi-Definite Program (BSDP) to achieve better computational efficiency, c) The feasible set of the MISDP was efficiently relaxed by replacing the positive semi-definite constraint with linear inequalities associated with a family of Fiedler vectors to compute a tighter upper bound for algebraic connectivity, d) Efficient neighborhood search heuristics based on greedy methods such as the k-opt and improved k-opt heuristics were developed, e) Variants of the problem occurring in UAV backbone networks and Air Transportation Management were considered in the dissertation along with numerical simulations corroborating the methodologies developed in this dissertation.