Improved bounds for data-gathering time in sensor networks

Many-to-one packet routing and scheduling are fundamental operations of sensor networks. It is well known that many sensor network applications rely on data collection from the nodes (the sensors) by a central processing device. There is a wide range of data gathering applications like: target and hazard detection, environmental monitoring, battlefield surveillance, etc. Consequently, efficient data collection solutions are needed to improve the performance of the network. In this paper, we assume a known distribution of sources (each node wants to transmit at most one packet) and one common destination (called base station). We provide via simple mathematical models, a transmission schedule for routing all the messages to the base station, jointly minimizing both the completion time and the average packet delivery time. We define our network model and provide improved lower bounds for linear, two-branch, and star (or multi-branch) network topologies. All our algorithms run in polynomial time. Finally, we prove that the problem of Quality of Service (QoS) in our setting for a star network under the same target function is NP-complete by showing a reduction from the 3-Set-Partition problem.