Abstract:
Energy
has been a major problem in a wireless sensor network. Consider
a field covered by sensors. Assume that every sensor shares
the same duty cycle and wake up once per duty cycle. When
a sensor wakes up, it detects the whether an event happens.
A sensor can only cover a small number of locations. A location
could be covered by more than one sensors. Now the task
is, to align the wakeup times of sensors covering a location
to be as evenly distributed across a duty cycle as possible.
An evenly distributed set of wakeup times has the best chance
to catch all the events. Several objective functions are
proposed to capture the nature of the problem. They all
have their advantages and shortages. The NPhardness of the
calculating the objective function is proved by a reduction
from kcoloring. Some impossibility results are proved, and
approximation algorithms are also proposed. To produce a
solution for realistic use, simulations on heuristics are
performed and analyzed.
Biography:
I
am a fourth year undergraduate student in department of
computer science, Tsinghua University. I spent my first
two years as a member of experimental class on mathematic
and physics of information school. I became a member of
the first Tsinghua-Microsoft joint special pilot class,
which focuses on both theory and practice of computer science
at the beginning of my third year. This autumn I will join
ITCS and start working for my Ph. D degree under the supervision
of Prof. Andrew Yao. I have enthusiasm and interest in computer
science. The topic of my final year project is wireless
sensor networks and probably I will continue researching
on this area in the next few years.