Abstract
Enhancing the connectivity of wireless sensor networks is necessary to avoid the occurrence of coverage gaps. In this paper, we aim at improving the network connectivity of a given network by adding a set of relays to it. We characterize the network connectivity by the Fiedler value, which is the second smallest eigenvalue of the Laplacian matrix representing the network graph. We propose a network-maintenance algorithm, which finds the best locations for a given set of relays. The proposed algorithm obtains the best relays' locations through a multi-level approach. In each level, the search problem can be formulated as a standard semi-definite programming (SDP) optimization problem. We show that the proposed algorithm can increase the average Fiedler value by 35% by adding one relay only.