A sub-gradient algorithm for maximal data extraction in energy-limited wireless sensor networks

We present an efficient and implementable algorithm for maximizing data extraction from energy limited wireless sensor networks. A distinguishing feature of this algorithm is that it arrives at efficient routing solutions after few iterations, which is vital for efficient performance in energy limited networks. The algorithm uses sub-gradient optimization to solve the dual of a data extraction problem constructed by relaxing the energy constraints. We show through computational experiments that, for the problem considered, both centralized and distributed versions of the algorithm arrive at routing solutions that are on average better than 10% from optimal after only 10 iterations.