This paper analyzes scheduling in a data gathering network with data compression. The nodes of the network collect some data and pass them to a single base station. Each node can, at some cost, preprocess the data before sending it, in order to decrease its size. Our goal is to transfer all data to the base station in given time, at the minimum possible cost. We prove that the decision version of this scheduling problem is NP-complete. Polynomial-time heuristic algorithms for solving the problem are proposed and tested in a series of computational experiments. 
Scheduling for data gathering networks with data compression