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 条
  • [21] Optimal Deployment Patterns for Full Coverage and k-Connectivity (k ≤ 6) Wireless Sensor Networks
    Yun, Ziqiu
    Bai, Xiaole
    Xuan, Dong
    Lai, Ten H.
    Jia, Weijia
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2010, 18 (03) : 934 - 947
  • [22] Random power control in wireless ad hoc networks
    Kim, TS
    Kim, SL
    IEEE COMMUNICATIONS LETTERS, 2005, 9 (12) : 1046 - 1048
  • [23] Approximation Theory for Connectivity of Ad Hoc Wireless Networks With Node Faults
    Takabe, Satoshi
    Wadayama, Tadashi
    IEEE WIRELESS COMMUNICATIONS LETTERS, 2019, 8 (04) : 1240 - 1243
  • [24] Approximating Minimum-Power k-Connectivity
    Nutov, Zeev
    AD HOC & SENSOR WIRELESS NETWORKS, 2010, 9 (1-2) : 129 - 137
  • [25] IMPACT OF THE DYNAMIC MEMBERSHIP IN THE CONNECTIVITY GRAPH OF THE WIRELESS AD HOC NETWORKS
    Doci, Arta
    Springer, William
    Xhafa, Fatos
    SCALABLE COMPUTING-PRACTICE AND EXPERIENCE, 2009, 10 (01): : 25 - 34
  • [26] DECK: A distributed, asynchronous and exact k-connectivity detection algorithm for Wireless Sensor Networks
    Akram, Vahid Khalilpour
    Dagdeviren, Orhan
    COMPUTER COMMUNICATIONS, 2018, 116 : 9 - 20
  • [27] On the connectivity in finite ad hoc networks
    Desai, M
    Manjunath, D
    IEEE COMMUNICATIONS LETTERS, 2002, 6 (10) : 437 - 439
  • [28] Complete Optimal Deployment Patterns for Full-Coverage and k-Connectivity (k ≤ 6) Wireless Sensor Networks
    Bai, Xiaole
    Xuan, Dong
    Yun, Ziqiu
    Lai, Ten H.
    Jia, Weijia
    MOBIHOC'08: PROCEEDINGS OF THE NINTH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING, 2008, : 401 - 410
  • [29] Exact probability of connectivity in one-dimensional ad hoc wireless networks
    Ghasemi, A
    Nader-Esfahani, S
    IEEE COMMUNICATIONS LETTERS, 2006, 10 (04) : 251 - 253
  • [30] Minimum power energy spanners in wireless ad hoc networks
    Abu-Affash, A. Karim
    Aschner, Rom
    Carmi, Paz
    Katz, Matthew J.
    WIRELESS NETWORKS, 2011, 17 (05) : 1251 - 1258
12345