Novel algorithms for the network lifetime problem in wireless settings |
| |
Authors: | Michael Elkin Yuval Lando Zeev Nutov Michael Segal Hanan Shpungin |
| |
Affiliation: | (1) Department of Computer Science, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel;(2) Department of Communication Systems Engineering, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel;(3) Computer Science Division, The Open University of Israel, 43107 Raanana, Israel;(4) Department of Computer Science, University of Calgary, Calgary, AB, T2N 1N4, Canada;; |
| |
Abstract: | One of the major concerns in wireless ad-hoc networks design is energy efficiency. Wireless devices are typically equipped with a limited energy supply sufficient only for a limited amount of time which is reversely proportional to the transmission power of the device. The network lifetime is defined as the time the first device runs out of its initial energy charge. In this paper we study the maximum network lifetime problem for broadcast and data gathering in wireless settings. We provide polynomial time approximation algorithms, with guaranteed performance bounds while considering omnidirectional and unidirectional transmissions. We also consider an extended variant of the maximum lifetime problem, which simultaneously satisfies additional constraints, such as bounded hop-diameter and degree of the routing tree, and minimizing the total energy used in a single transmission. Finally, we evaluate the performance of some of our algorithms through simulations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|