Improved approximation algorithms for maximum lifetime problems in wireless networks

Zeev Nutov

doi:10.1016/j.tcs.2011.08.001

Improved approximation algorithms for maximum lifetime problems in wireless networks

2012-09-01

4

OA

AI

DOI：10.1016/j.tcs.2011.08.001

原文链接

查看原文

摘要

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.

Keyword:

Minimal energy control

Optimization methods

Ad-hoc networks

Low power algorithms and protocols

Sensor networks

Improved approximation algorithms for maximum lifetime problems in wireless networks

摘要

AI总结

期刊

机构

引用论文