Energy-Effcient Protocols in Wireless Sensor Networks

importance. It not only opens new dimensions in the availability of highbandwidth
connections in particular for mobile applications, but also more
and more replaces so far 'wired' network installations. While the spatial
aspect was already of interest in the wired network world due to cable
costs etc., it has far more influence on the design and operation of wireless
networks. The power required to transmit information via radio waves
is heavily dependent on the Euclidean distance of sender and receivers.
Hence problems in this area are prime candidates for the use of techniques
from computational geometry.
We consider the problem of assigning powers to nodes of a wireless
network in the plane such that a message originating from specific source
node s reaches all other nodes within a bounded number k transmissions
and the total amount of assigned energy is minimized. We present (1+E)-
approximation algorithm, with running time linear in n, which is drastic
improvement upon the previous best know algorithm.