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

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

3 Citations (Scopus)

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. © 2004 Elsevier B.V. All rights reserved.

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

Research Keywords

Ad hoc wireless network
Approximation algorithms
Min power symmetric connectivity

Access Output

10.1016/j.tcs.2004.06.017Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{a88d707830944e0aa220df0fe1f41daa,

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. {\textcopyright} 2004 Elsevier B.V. All rights reserved.",

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 = "English",

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. © 2004 Elsevier B.V. All rights reserved.

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. © 2004 Elsevier B.V. All rights reserved.

KW - Ad hoc wireless network

KW - Approximation algorithms

KW - Min power symmetric connectivity

UR - http://www.scopus.com/inward/record.url?scp=5144223046&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-5144223046&origin=recordpage

U2 - 10.1016/j.tcs.2004.06.017

DO - 10.1016/j.tcs.2004.06.017

M3 - RGC 21 - Publication in refereed journal

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

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this