.png){kind=icon}
.png){kind=icon}
Return
Improved approximation algorithms for maximum lifetime problems in wireless networks
.png){kind=icon}
OA
AI
DOI：10.1016/j.tcs.2011.08.001.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A 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 is an element of E, node capacity b(v) (the battery charge of v) for every v is an element of V. and a root r. The goal is to find a maximum size collection {T-1, ... , T-k} of Broadcast/Convergecast trees rooted at r such that Sigma(k)(i=1) w(delta(Ti)(v)) <= b(v), where delta(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 T-i 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 Omega(left perpendicular1/log nright perpendicular) 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 gamma >= 0, and the goal is to find the maximum integer k so that k Broadcast and gamma k Convergecast rounds can be performed. We also consider the model with partial level aggregation. (C) 2011 Elsevier B.V. All rights reserved.
Keywords:
Minimal energy control
Optimization methods
Ad-hoc networks
Low power algorithms and protocols
Sensor networks
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.