Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

Xiaohua Jia (), Dongsoo Kim (), Sam Makki (), Peng-Jun Wan () and Chih-Wei Yi ()
Additional contact information
Xiaohua Jia: Wuhan University and City University of Hong Kong
Dongsoo Kim: Indiana Uiversity Purdue University
Sam Makki: University of Toledo
Peng-Jun Wan: Illinois Institute of Technology
Chih-Wei Yi: Illinois Institute of Technology

Journal of Combinatorial Optimization, 2005, vol. 9, issue 2, No 6, 213-222

Abstract: 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≥, 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 (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-6858-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:9:y:2005:i:2:d:10.1007_s10878-005-6858-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-6858-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().