Relay augmentation for lifetime extension of wireless sensor networks

Abstract

The authors 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 through 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 sp..