Tightening the upper bound for the minimum energy broadcasting

被引：8

作者：

Flammini, Michele ^{[1
]}

Klasing, Ralf ^{[2
]}

Navarra, Alfredo ^{[1
]}

Perennes, Stephane ^{[3
]}

机构：

[1] Univ Aquila, Dept Comp Sci, I-67100 Laquila, Italy

[2] Univ Bordeaux 1, LaBRI, CNRS, F-33405 Talence, France

[3] Univ Nice, MASCOTTE Project I3S, CNRS, INRIA, F-06108 Nice 2, France

来源：

WIRELESS NETWORKS | 2008年 / 14卷 / 05期

关键词：

minimums panning tree; approximation factor; multi-hop; ad hoc networks;

D O I：

10.1007/s11276-006-0007-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we present a new upper bound on the approximation ratio of the Minimum Spanning Tree heuristic for the basic problem on Ad-Hoc Networks given by the Minimum Energy Broadcast Routing (MEBR). We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound [4], almost closing the gap with the lower bound of 6 [12].

引用

页码：659 / 669

页数：11

共 13 条

[1]

CLEMENTI A, 2003, P 3 IEEE IPDPS WORKS

[2]

Clementi A. E. F., 2001, STACS 2001. 18th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings (Lecture Notes in Computer Science Vol.2010), P121

[3]

DAS AK, 2003, P IEEE INFOCOM 2003, V2, P1001

[4]

Flammini M, 2005, LECT NOTES COMPUT SC, V3503, P22

[5]

Flammini M., 2004, P ACM JOINT WORKSH F, P85

[6] Iterated local optimization for minimum energy broadcast [J].

Kang, I ;

Poovendran, R .

PROCEEDINGS OF THE THIRD INTERNATIONAL SYMPOSIUM ON MODELING AND OPTIMIZATION IN MOBILE, AD HOC, AND WIRELESS NETWORKS, 2005, :332-341

[7]

Klasing R, 2004, LECT NOTES COMPUT SC, V3042, P866

[8] On minimum-energy broadcasting in all-wireless networks [J].

Li, FL ;

Nikolaidis, L .

LCN 2001: 26TH ANNUAL IEEE CONFERENCE ON LOCAL COMPUTER NETWORKS, PROCEEDINGS, 2001, :193-202

[9] Tighter bounds for the minimum energy broadcasting problem [J].

Navarra, A .

Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005, :313-322

[10]

Rappaport T. S., 1996, WIRELESS COMMUNICATI

← 1 2 →