Nested Partitioning for the Minimum Energy Broadcast Problem

被引：13

作者：

Al-Shihabi, Sameh ^{[1
]}

Merz, Peter ^{[2
]}

Wolf, Steffen ^{[2
]}

机构：

[1] Univ Jordan, Dept Ind Engn, Amman 11942, Jordan

[2] Univ Kaiserslautern, Distributed Algorithms Grp, D-67663 Kaiserslautern, Germany

来源：

LEARNING AND INTELLIGENT OPTIMIZATION | 2008年 / 5313卷

关键词：

D O I：

10.1007/978-3-540-92695-5_1

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The problem of finding the broadcast scheme with minimum power consumption in a wireless ad-hoc network is NP-hard. This work presents a new hybrid algorithm to solve this problem by combining Nested Partitioning with Local Search and Linear Programming. The algorithm is benchmarked by solving instances with 20 and 50 nodes where results are compared to either optimum or best results found by an IP solver. In these instances, the proposed algorithm was able to find optimal and near optimal solutions.

引用

页码：1 / +

页数：2

共 18 条

[1]

ALSHIHABI S, 2004, HYBRID METAHEURISTIC, P11

[2]

Ambühl C, 2005, LECT NOTES COMPUT SC, V3580, P1139

[3]

CAGALJ M, 2002, MOBICOM 2002, P172

[4]

Clementi A, 2001, LNCS, V2001, P121

[5]

Das AK, 2003, GLOB TELECOMM CONF, P523

[6]

Das AK, 2003, IEEE INFOCOM SER, P1001

[7]

Haas ZJ, 1998, IEEE MILIT COMMUN C, P187, DOI 10.1109/MILCOM.1998.722569

[8]

Kang I, 2004, GLOB TELECOMM CONF, P4114

[9] 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

[10]

MONTEMANNI R, 2005, WIR COMM NETW C, V4, P2057

← 1 2 →