Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

被引：0
|
作者：
Xiaohua Jia
Dongsoo Kim
Sam Makki
Peng-Jun Wan
Chih-Wei Yi
机构：
[1] Wuhan University and City University of Hong Kong,School of Computing and Department of Computer Science
[2] Indiana Uiversity Purdue University,Department of Electrical and Computer Engineering
[3] University of Toledo,Department of Electrical Engineering and Computer Science
[4] Illinois Institute of Technology,Department of Computer Science
[5] City University of Hong Kong,Department of Computer Science
来源：
Journal of Combinatorial Optimization | 2005年 / 9卷
关键词：
-connectivity; power assignment; wireless ad hoc sensor networks;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：213 / 222
页数：9
相关论文
共 50 条
  • [1] Power assignment for k-connectivity in wireless ad hoc networks
    Jia, XH
    Kim, D
    Makki, S
    Wan, PJ
    Yi, CW
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (02) : 213 - 222
  • [2] Power assignment for k-connectivity in wireless ad hoc networks
    Jia, XH
    Kim, D
    Makki, S
    Wan, PJ
    Yi, CW
    IEEE INFOCOM 2005: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-4, PROCEEDINGS, 2005, : 2206 - 2211
  • [3] Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks
    Gruia Calinescu
    Peng-Jun Wan
    Mobile Networks and Applications, 2006, 11 : 121 - 128
  • [4] Range assignment for biconnectivity and k-Edge Connectivity in wireless ad hoc networks
    Calinescu, Gruia
    Wan, Peng-Jun
    MOBILE NETWORKS & APPLICATIONS, 2006, 11 (02) : 121 - 128
  • [5] Asymptotic critical total power for k-connectivity of wireless networks
    Zhang, Honghai
    Hou, Jennifer C.
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2008, 16 (02) : 347 - 358
  • [6] Analysis of k-Connectivity of a Cognitive Radio Ad-Hoc Network
    Abbagnale, Anna
    Cuomo, Francesca
    Cipollone, Emanuele
    PE-WASUN09: PROCEEDINGS OF THE SIXTH ACM INTERNATIONAL SYMPOSIUM ON PERFORMANCE EVALUATION OF WIRELESS AD-HOC, SENSOR, AND UBIQUITOUS NETWORKS, 2009, : 124 - 131
  • [7] Minimum power assignment in wireless ad hoc networks with spanner property
    Wang, Y
    Li, XY
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2006, 11 (01) : 99 - 112
  • [8] Minimum power assignment in wireless ad hoc networks with spanner property
    Yu Wang
    Xiang-Yang Li
    Journal of Combinatorial Optimization, 2006, 11 : 99 - 112
  • [9] Max-Life Power Schedule for Connectivity and Biconnectivity in Wireless Ad Hoc Networks
    Peng-Jun Wan
    Chih-Wei Yi
    Mobile Networks and Applications, 2005, 10 : 997 - 1004
  • [10] Connectivity in Cooperative Wireless Ad Hoc Networks
    Wang, Liaoruo
    Liu, Benyuan
    Goeckel, Dennis
    Towsley, Don
    Westphal, Cedric
    MOBIHOC'08: PROCEEDINGS OF THE NINTH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING, 2008, : 121 - 130
12345