Performance evaluation for energy efficient topologic control in ad hoc wireless networks

Minming Li; Shawn L. Huang; Xiaoming Sun; Xiao Huang

doi:10.1016/j.tcs.2004.06.017

Performance evaluation for energy efficient topologic control in ad hoc wireless networks

Minming Li^*
, Shawn L. Huang
, Xiaoming Sun
, Xiao Huang

^*此作品的通讯作者

Tsinghua University
3M

科研成果: 期刊稿件 › 文章 › 同行评审

3 引用（Scopus）

摘要

Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρ_k for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρ_k for all k.

源语言	英语
页（从-至）	399-408
页数	10
期刊	Theoretical Computer Science
卷	326
期	1-3
DOI	https://doi.org/10.1016/j.tcs.2004.06.017
出版状态	已出版 - 20 10月 2004
已对外发布	是

访问文件

10.1016/j.tcs.2004.06.017

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{aa4d4f85185b4c18a541b1902f30db75,

title = "Performance evaluation for energy efficient topologic control in ad hoc wireless networks",

abstract = "Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.",

keywords = "Ad hoc wireless network, Approximation algorithms, Min power symmetric connectivity",

author = "Minming Li and Huang, \{Shawn L.\} and Xiaoming Sun and Xiao Huang",

year = "2004",

month = oct,

day = "20",

doi = "10.1016/j.tcs.2004.06.017",

language = "英语",

volume = "326",

pages = "399--408",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Performance evaluation for energy efficient topologic control in ad hoc wireless networks

AU - Li, Minming

AU - Huang, Shawn L.

AU - Sun, Xiaoming

AU - Huang, Xiao

PY - 2004/10/20

Y1 - 2004/10/20

N2 - Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.

AB - Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.

KW - Ad hoc wireless network

KW - Approximation algorithms

KW - Min power symmetric connectivity

UR - https://www.scopus.com/pages/publications/5144223046

U2 - 10.1016/j.tcs.2004.06.017

DO - 10.1016/j.tcs.2004.06.017

M3 - 文章

AN - SCOPUS:5144223046

SN - 0304-3975

VL - 326

SP - 399

EP - 408

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Performance evaluation for energy efficient topologic control in ad hoc wireless networks

摘要

访问文件

其它文件与链接

学术指纹

引用此