Power assignment for k-connectivity in wireless ad hoc networks

Xiaohua Jia*, Dongsoo Kim, Sam Makki, Peng Jun Wan, Tsì-Uí İk

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

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 languageEnglish
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Pages2206-2211
Number of pages6
DOIs
StatePublished - 10 Oct 2005
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: 13 Mar 200517 Mar 2005

Publication series

NameProceedings - IEEE INFOCOM
Volume3
ISSN (Print)0743-166X

Conference

ConferenceIEEE INFOCOM 2005
CountryUnited States
CityMiami, FL
Period13/03/0517/03/05

Keywords

  • K-connectivity
  • Power assignment
  • Wireless ad hoc sensor networks

Fingerprint Dive into the research topics of 'Power assignment for k-connectivity in wireless ad hoc networks'. Together they form a unique fingerprint.

  • Cite this

    Jia, X., Kim, D., Makki, S., Wan, P. J., & İk, T-U. (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 - 24th Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 2206-2211). (Proceedings - IEEE INFOCOM; Vol. 3). https://doi.org/10.1109/INFCOM.2005.1498495