Date Added: Nov 2012
Network longevity and connectivity are key design goals in any wireless sensor network deployment. In this paper, the authors consider the placement of relay nodes and individual transmission power assignments. Specifically, given a planar deployment of sensors and a base station, they seek the placement of a limited number of relays and optimal sensor power assignments such that the network is connected. They present a polynomial-time bi-criteria approximation algorithm for this problem. They also provide an optimal O(n2 log n)-time algorithm for a restricted version where nodes lie on a simplified urban grid (that they call a comb-grid). They also study a related variant that assumes fixed transmission power values, with the goal of minimizing the number of relays.