Improved approximation algorithms for maximum lifetime problems in wireless networks

Zeev Nutov, Michael Segal

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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∈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 Ω(⌊1logn⌋) 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.

שפה מקוריתאנגלית
עמודים (מ-עד)88-97
מספר עמודים10
כתב עתTheoretical Computer Science
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 ספט׳ 2012

הערה ביבליוגרפית

Funding Information:
We thank anonymous referees for their valuable comments that significantly improved the presentation of the paper. The second author was supported in part by US Air Force, European Office of Aerospace Research and Development, Grant# FA8655-09-1-3016.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Improved approximation algorithms for maximum lifetime problems in wireless networks'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי