Tighter bounds for the minimum energy broadcasting problem

被引：15

作者：

Navarra, A ^{[1
]}

机构：

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

来源：

Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks | 2005年

关键词：

D O I：

10.1109/WIOPT.2005.51

中图分类号：

TN [电子技术、通信技术];

学科分类号：

0809 ;

摘要：

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) problem. 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 [3].

引用

页码：313 / 322

页数：10

共 8 条

[1]

Clementi A, 2001, LNCS, V2001, P121

[2]

CLEMENTI A, 2003, P 3 IEEE IPDPS WORKS

[3]

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

[4]

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

[5]

Rappaport T. S., 1996, WIRELESS COMMUNICATI

[6]

ROSSI G, 2002, THESIS U STUDI SIENA

[7] Minimum-energy broadcasting in static ad hoc wireless networks [J].

Wan, PJ ;

Calinescu, G ;

Li, XY ;

Frieder, O .

WIRELESS NETWORKS, 2002, 8 (06) :607-617

[8]

Wieselthier J. E., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P585, DOI 10.1109/INFCOM.2000.832232

← 1 →