On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks: NP-Completeness and Approximation Algorithm
Energy efficiency is critical for wireless sensor networks. The data gathering process must be carefully designed to conserve energy and extend the network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this paper, the authors study the construction of a data gathering tree to maximize the network lifetime, which is defined as the time until the first node depletes its energy.