Power assignment for k-connectivity in wireless ad hoc networks

被引：54

作者：

Jia, XH ^{[1
]}

Kim, D

Makki, S

Wan, PJ

Yi, CW

机构：

[1] Wuhan Univ, Sch Comp, Wuhan, Peoples R China

[2] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[3] Indiana Univ Purdue Univ, Dept Elect & Comp Engn, Indianapolis, IN 46202 USA

[4] Univ Toledo, Dept Elect Engn & Comp Sci, Toledo, OH USA

[5] IIT, Dept Comp Sci, Chicago, IL 60616 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 02期

基金：

美国国家科学基金会;

关键词：

k-connectivity; power assignment; wireless ad hoc sensor networks;

D O I：

10.1007/s10878-005-6858-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：213 / 222

页数：10

共 15 条

[1]

[Anonymous], 2003, P 9 ANN INT C MOB CO

[2] A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph [J].