Announcements:
Instructor:
Matya
Katz (
matya@cs.bgu.ac.il )
Office hours: TBA, Deichmann building (58), room 315, Tel: (08) 6461628
Teaching
Assistant:
Office
hours:
Class
Time:
Wednesday 12-14 (building 28, room 301)
Course
Description:
Several projects
will be
offered dealing with power assignment (alternatively, range assignment)
in
radio networks. Let P be a set of n points in the plane, representing n
transmitters-receivers (or transmitters for short). In the general
version
of the power assignment problem one needs to assign transmission ranges
to the
transmitters in P, so that (i) the resulting communication graph is strongly
connected;
that is, for any two transmitters p1 and
p2 in P, there exists a sequence of transmitters (i.e., a path)
p1=q1,q2,…,qk=p2, such that q2 is within
range
r(q1) from q1, q3 is within range r(q2) from q2, etc., where r(qi) is the range that was assigned to qi,
and (ii) the total power consumption
(i.e., the cost of the assignment of ranges) is minimized, where the
total
power consumption is a function of the form sum_{p in P} r(p)^a, where
a is a
constant typically between 2 and 5. The general version of the power
assignment
problem is known to be NP-hard, and the best approximation that is
known is a
2-approximation.
In practice,
though, it is
usually impossible to assign arbitrary power levels (ranges) to the
transmitters
of a radio network. Instead one can only choose from a small number of
preset
power levels, corresponding to a small number of ranges. We refer to
this more
realistic version of the power assignment problem as the power
assignment
problem with c power levels (where c > 1 stands for a small
constant
number).
In a typical
project, the
students will have to develop and implement algorithms and/or
heuristics for
efficiently solving one of several variants of the power assignment
problem.
Below is a
selection of
papers dealing with the power assignment problem from a theoretical
point of view. For some of the projects, it
might be helpful to
``peek'' at one or more of these papers.
L. M. Kirousis,
E. Kranakis, D. Krizanc,
and A. Pelc.
Power
consumption in packet radio networks.
14th
Annual Sympos. Theoretical Aspects
of Computer Science (STACS),
1997, 363-374, LNCS 1200.
Paper on the
minimum energy
broadcast tree problem (to be added).
P. Carmi and
M.J. Katz.
Power assignment
in radio
networks with two power levels.
Proc. 9th
Scandinavian Workshop on Algorithm Theory, 2004, 431—441, LNCS 3111.