TY - CHAP
T1 - Improved approximation bounds for maximum lifetime problems in wireless ad-hoc network
AU - Lee, Sang Hyuk
AU - Radzik, Tomasz
PY - 2012
Y1 - 2012
N2 - A wireless ad-hoc network consists of a number of wireless devices (nodes), that communicate with each other within the network using their built-in radio transceivers. The nodes are in general battery-powered, thus their lifetime is limited. Therefore, algorithms for maximizing the network lifetime are of great interest. In this paper we consider the Rooted Maximum Network Lifetime (RMNL) problems: given a network N and a node r, the objective is to find a maximum-size collection of routing trees rooted at the node r for a specified communication pattern. The number of such trees represents the total number of communication rounds executed before the first node in the network dies due to battery depletion. We consider two communication patterns, broadcast and convergecast. We follow the approach used by Nutov and Segal in [15], who developed polynomial time approximation algorithms with constant approximation ratios for the broadcast and convergecast RMNL problems. Our analysis of their algorithms leads to better approximation ratios than the ratios derived in [15]. In particular, we show a 1/7 approximation ratio for the multiple topology convergecast RMNL problem, improving the previous ratio of 1/31.
AB - A wireless ad-hoc network consists of a number of wireless devices (nodes), that communicate with each other within the network using their built-in radio transceivers. The nodes are in general battery-powered, thus their lifetime is limited. Therefore, algorithms for maximizing the network lifetime are of great interest. In this paper we consider the Rooted Maximum Network Lifetime (RMNL) problems: given a network N and a node r, the objective is to find a maximum-size collection of routing trees rooted at the node r for a specified communication pattern. The number of such trees represents the total number of communication rounds executed before the first node in the network dies due to battery depletion. We consider two communication patterns, broadcast and convergecast. We follow the approach used by Nutov and Segal in [15], who developed polynomial time approximation algorithms with constant approximation ratios for the broadcast and convergecast RMNL problems. Our analysis of their algorithms leads to better approximation ratios than the ratios derived in [15]. In particular, we show a 1/7 approximation ratio for the multiple topology convergecast RMNL problem, improving the previous ratio of 1/31.
KW - Approximation algorithm
KW - Broadcast
KW - Convergecast
KW - Network Lifetime
KW - Wireless ad-hoc network
UR - http://www.scopus.com/inward/record.url?scp=84864821267&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31638-8_2
DO - 10.1007/978-3-642-31638-8_2
M3 - Conference paper
AN - SCOPUS:84864821267
SN - 9783642316371
VL - 7363 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 14
EP - 27
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
T2 - 11th International Conference on Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW2012
Y2 - 9 July 2012 through 12 July 2012
ER -