Improved approximation algorithms for maximum lifetime problems in wireless networks

AbstractA wireless ad-hoc network consists of a collection of transceivers positioned in the plane. Each transceiver is equipped with a limited battery charge. The battery charge is reduced after each transmission, depending on the transmission distance. One of the major problems in wireless network design is to route network traffic efficiently, so as to maximize the network lifetime, i.e., the number of successful transmission rounds. In this paper, we consider Rooted Maximum Lifetime Broadcast/Convergecast problems in wireless settings. The instance consists of a directed graph G=(V,E) with edge-weight w(e) (the power needed to transmit a message along e) for every e∈E, node capacity b(v) (the battery charge of v) for every v∈V, and a root r. The goal is to find a maximum size collection {T1,…,Tk} of Broadcast/Convergecast trees rooted at r such that ∑i=1kw(δTi(v))≤b(v), where δT(v) is the set of edges leaving v in T. In the Single Topology version, the same tree is used to transmit all the messages, namely, all the Broadcast/Convergecast trees Ti are identical. Using recent work on degree constrained network design problems (Nutov, 2008) [26], we give constant ratio approximation algorithms for various broadcast and convergecast problems, improving the previously best known approximation Ω(⌊1/logn⌋) by Elkin et al. (2011) [12]. Similar results are shown for the more general Rooted Maximum Lifetime Mixedcast problem, where in addition we are given an integer γ≥0, and the goal is to find the maximum integer k so that k Broadcast and γk Convergecast rounds can be performed. We also consider the model with partial level aggregation