  We propose a novel relay augmentation strategy for extending the lifetime of
a certain class of wireless sensor networks. In this class sensors are located
at fixed and pre-determined positions and all communication takes place via
multi-hop paths in a fixed routing tree rooted at the base station. It is
assumed that no accumulation of data takes place along the communication paths
and that there is no restriction on where additional relays may be located.
Under these assumptions the optimal extension of network lifetime is modelled
as the Euclidean $k$-bottleneck Steiner tree problem. Only two approximation
algorithms for this NP-hard problem exist in the literature: a minimum spanning
tree heuristic (MSTH) with performance ratio 2, and a probabilistic 3-regular
hypergraph heuristic (3RHH) with performance ratio $\sqrt{3}+\epsilon$. We
present a new iterative heuristic that incorporates MSTH and show via
simulation that our algorithm performs better than MSTH in extending lifetime,
and outperforms 3RHH in terms of efficiency.
