TITLE: New approximation bounds for some Maximum Network Lifetime problems in wireless ad-hoc networks
SPEAKER: Tomasz Radzik (Algorithm Design Group, Department of Computer Science, 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 and known initial capacities of node batteries, and for 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 node batteries are sufficient to execute all rounds. For example, the communication task can be 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 three types of communication tasks: broadcast, convergecast and unicast. 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.