Tomasz Radzik
King's College London
New approximation bounds for some Maximum Network Lifetime problems in
wireless ad-hoc networks
A wireless ad-hoc network consists of a number of wireless devices
(nodes) that communicate with each other using built-in radio
transceivers. The nodes are commonly battery-powered, so their lifetime
is limited, but the operation of the whole network can be extended, if
appropriate communication algorithms are selected. From a number of
possible models, we consider the following Maximum Network Lifetime
(MNL) problems. For a given (static) network N with known node-to-node
communication costs and 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 battery capacities are sufficient to execute
all rounds. For example, the communication task can be gathering sensor
data from the network in one specified node (convergecast), and we would
like to execute this task periodically, as many times as possible. 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.
Joint work with Sang Hyuk Lee