New approximation bounds for some Maximum Network Lifetime problems

5^th November 2013, 16:00 Ashton Lecture Theater
Dr. Tomasz Radzik
Department of Informatics
King's College London

Abstract

We consider the following Maximum Network Lifetime (MNL) problems, which may arise in the context of ad-hoc wireless networks. For a given (static) network N with known node-to-node communication costs, known initial capacities of node batteries, and a specified communication task, design a maximum number of communication rounds such that: (i) each round executes this specified communication task, and (ii) the initial capacities of the node batteries are sufficient to execute all rounds. The communication task can be, for example, gathering sensor data from the network in one specified node, and we would like to execute this task periodically, as many times as possible before the first node battery is depleted. We show improved approximation algorithms for the MNL problems for the three basic communication tasks - broadcast, convergecast (gathering of data) and unicast - and for "mixedcast" (a combination of the three). For example, we show a polynomial-time algorithm which computes 1/7-approximation solutions for the convergecast MNL problem, improving on the previous ratio of 1/31.