  We study the problem of building a maximum lifetime data collection tree for
periodic convergecast applications in wireless sensor networks. We
experimentally observe that if two nodes transmit same number of data packets,
the amount of energy consumption of the nodes is approximately the same even if
the payload lengths of the transmitted packets are different. This is because
the major energy consumption during a packet transmission arises from radio
start-up and medium access control overhead. Our formulated lifetime
maximization problem captures the energy expenditure due to message
transmissions/ receptions in terms of the number of data packets transmitted/
received, in contrast to prior works, which consider the number of data units
(amount of sensor data generated by a node) transmitted/ received. Variable
transmission power levels of the radio and accounting for the sensor energy
consumption are other factors that make our problem formulation different from
those in prior work. We prove that this problem is NP-complete and propose an
algorithm to solve it. The performance of the proposed algorithm is
experimentally evaluated using Jain's fairness index as a metric by
implementing it on an actual testbed consisting of 20 sensor nodes and compared
with those of the widely used shortest path tree (SPT) and random data
collection tree (RDCT) algorithms. The energy consumption of different nodes
under the proposed algorithm are shown to be more balanced than under SPT and
RDCT algorithms. Also, the performance of the proposed algorithm in large
networks is studied through simulations and is compared with those of the
state-of-the-art RaSMaLai algorithm, SPT, minimum spanning tree, and RDCT based
data collection schemes. Our simulations show that the proposed algorithm
provides a significantly higher network lifetime compared to all the other
considered data collection approaches.
