|
UWEETR-2005-0004 Author(s): Keywords: Abstract We consider the problem of survivable minimum power bidirectional topology optimization in wireless networks. Three different optimization problems are considered, minimizing the total transmit power, minimizing the maximum transmit power and the minimum spanning tree, 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 critical result, we show how each of the three 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. |