Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

Xiaohua Jia; Dongsoo Kim; Sam Makki; Peng-Jun Wan; Chih-Wei Yi

doi:10.1109/INFCOM.2005.1498495

Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

Xiaohua Jia, Dongsoo Kim, Sam Makki, Peng-Jun Wan, Chih-Wei Yi

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

40 Citations (Scopus)

Abstract

The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k))-approximation algorithm for k (2k - 1) ≤ n where n is the network size, a (k + 2 [(k + 1) /2])-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.

Original language	English
Title of host publication	Proceedings - IEEE Infocom 2005: The Conference on Computer Communications
Subtitle of host publication	24^th Annual Joint Conference of the IEEE Computer and Communications Societies
Editors	Kia Makki, Edward Knightly
Pages	2206-2211
Volume	3
DOIs	https://doi.org/10.1109/INFCOM.2005.1498495
Publication status	Published - Mar 2005
Event	IEEE INFOCOM 2005 - Hyatt Regency Miami, Miami, United States Duration: 13 Mar 2005 → 17 Mar 2005

Publication series

Name
ISSN (Print)	0743-166X

Conference

Conference	IEEE INFOCOM 2005
Place	United States
City	Miami
Period	13/03/05 → 17/03/05

Research Keywords

K-connectivity
Power assignment
Wireless ad hoc sensor networks

Access Output

10.1109/INFCOM.2005.1498495

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Jia, X., Kim, D., Makki, S., Wan, P.-J., & Yi, C.-W. (2005). Power Assignment for k-Connectivity in Wireless Ad Hoc Networks. In K. Makki, & E. Knightly (Eds.), Proceedings - IEEE Infocom 2005: The Conference on Computer Communications: 24^th Annual Joint Conference of the IEEE Computer and Communications Societies (Vol. 3, pp. 2206-2211) https://doi.org/10.1109/INFCOM.2005.1498495

@inproceedings{4a8822e81bc34fee8c2fabda6ffc339f,

title = "Power Assignment for k-Connectivity in Wireless Ad Hoc Networks",

abstract = "The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k))-approximation algorithm for k (2k - 1) ≤ n where n is the network size, a (k + 2 [(k + 1) /2])-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.",

keywords = "K-connectivity, Power assignment, Wireless ad hoc sensor networks",

author = "Xiaohua Jia and Dongsoo Kim and Sam Makki and Peng-Jun Wan and Chih-Wei Yi",

year = "2005",

month = mar,

doi = "10.1109/INFCOM.2005.1498495",

language = "English",

isbn = "0780389689",

volume = "3",

pages = "2206--2211",

editor = "Kia Makki and Edward Knightly",

booktitle = "Proceedings - IEEE Infocom 2005: The Conference on Computer Communications",

note = "IEEE INFOCOM 2005 ; Conference date: 13-03-2005 Through 17-03-2005",

}

Jia, X, Kim, D, Makki, S, Wan, P-J & Yi, C-W 2005, Power Assignment for k-Connectivity in Wireless Ad Hoc Networks. in K Makki & E Knightly (eds), Proceedings - IEEE Infocom 2005: The Conference on Computer Communications: 24^th Annual Joint Conference of the IEEE Computer and Communications Societies. vol. 3, pp. 2206-2211, IEEE INFOCOM 2005, Miami, Florida, United States, 13/03/05. https://doi.org/10.1109/INFCOM.2005.1498495

Power Assignment for k-Connectivity in Wireless Ad Hoc Networks. / Jia, Xiaohua; Kim, Dongsoo; Makki, Sam et al.
Proceedings - IEEE Infocom 2005: The Conference on Computer Communications: 24^th Annual Joint Conference of the IEEE Computer and Communications Societies. ed. / Kia Makki; Edward Knightly. Vol. 3 2005. p. 2206-2211.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

AU - Jia, Xiaohua

AU - Kim, Dongsoo

AU - Makki, Sam

AU - Wan, Peng-Jun

AU - Yi, Chih-Wei

PY - 2005/3

Y1 - 2005/3

N2 - The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k))-approximation algorithm for k (2k - 1) ≤ n where n is the network size, a (k + 2 [(k + 1) /2])-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.

AB - The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k))-approximation algorithm for k (2k - 1) ≤ n where n is the network size, a (k + 2 [(k + 1) /2])-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.

KW - K-connectivity

KW - Power assignment

KW - Wireless ad hoc sensor networks

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

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

U2 - 10.1109/INFCOM.2005.1498495

DO - 10.1109/INFCOM.2005.1498495

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 0780389689

VL - 3

SP - 2206

EP - 2211

BT - Proceedings - IEEE Infocom 2005: The Conference on Computer Communications

A2 - Makki, Kia

A2 - Knightly, Edward

T2 - IEEE INFOCOM 2005

Y2 - 13 March 2005 through 17 March 2005

ER -

Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this