Power Assignment for k-Connectivity in Wireless Ad Hoc Networks
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 213-222 |
| Journal / Publication | Journal of Combinatorial Optimization |
| Volume | 9 |
| Issue number | 2 |
| Publication status | Published - Mar 2005 |
Link(s)
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.
Research Area(s)
- k-connectivity, Power assignment, Wireless ad hoc sensor networks
Citation Format(s)
Power Assignment for k-Connectivity in Wireless Ad Hoc Networks. / JIA, Xiaohua; KIM, Dongsoo; MAKKI, Sam; WAN, Peng-Jun; YI, Chih-Wei.
In: Journal of Combinatorial Optimization, Vol. 9, No. 2, 03.2005, p. 213-222.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
