K-node connected power efficient topologies in wireless networks: a semidefinite programming approach

We consider the problem of survivable minimum power bidirectional topology optimization in wireless networks. Two optimization problems are considered, minimization of the total transmit power and minimization of the maximum transmit power, subject to arbitrary K-node connectivity constraints. In this paper, we take an algebraic view of graph connectivity which is defined as the second smallest eigenvalue of the Laplacian matrix of a graph. Since the algebraic connectivity of a graph is known to be a lower bound on its node and edge connectivities, we impose a constraint on the algebraic connectivity to ensure that the solution is K-connected. Given the special properties of the Laplacian matrix of a graph, it is possible to express the algebraic connectivity requirement as a positive semidefinite constraint. Using this result, we show how the optimization problems can be formulated as 0/1 semidefinite programs (SDP´s), which can be solved exactly using an SDP solver within a branch-and-bound framework. Linear and semidefinite relaxations of the 0/1 constraints are also discussed. These relaxations are useful for generating lower bounds on the exact 0/1 SDP models.