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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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.

Original language	English
Pages (from-to)	399-408
Number of pages	10
Journal	Theoretical Computer Science
Volume	326
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2004.06.017
State	Published - 20 Oct 2004
Externally published	Yes

Keywords

Ad hoc wireless network
Approximation algorithms
Min power symmetric connectivity

Access to Document

10.1016/j.tcs.2004.06.017

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this