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 条
  • [41] Comments on On the connectivity in finite ad hoc networks""
    Dept. of Electrical Eng., Indian Institute of Technology -Bombay, Mumbai, India
    IEEE Commun Lett, 2006, 2 (88-90): : 88 - 90
  • [42] Comments on "On the connectivity in finite ad hoc networks"
    Gore, AD
    IEEE COMMUNICATIONS LETTERS, 2006, 10 (02) : 88 - 90
  • [43] Techniques for maintaining connectivity in wireless ad-hoc networks under energy constraints
    Koushanfar, Farinaz
    Davare, Abhijit
    Nguyen, David T.
    Sangiovanni-Vincentelli, Alberto
    Potkonjak, Miodrag
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2007, 6 (03) : 16
  • [44] Impact of interferences on connectivity in Ad Hoc Networks
    Dousse, O
    Baccelli, F
    Thiran, P
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2005, 13 (02) : 425 - 436
  • [45] Connectivity in wireless ad-hoc networks with a log-normal radio model
    Hekmat, R
    Van Mieghem, P
    MOBILE NETWORKS & APPLICATIONS, 2006, 11 (03) : 351 - 360
  • [46] Connectivity in Wireless Ad-hoc Networks with a Log-normal Radio Model
    R. Hekmat
    P. Van Mieghem
    Mobile Networks and Applications, 2006, 11 : 351 - 360
  • [47] Connectivity in vehicular ad hoc networks in presence of wireless mobile base-stations
    Yousefi, Saleh
    Altman, Eitan
    El-Azouzi, Rachid
    Fathy, Mahmood
    2007 7TH INTERNATIONAL CONFERENCE ON ITS TELECOMMUNICATIONS, PROCEEDINGS, 2007, : 85 - +
  • [48] The κk-connectivity of line graphs
    Li, Hengzhe
    Lu, Yuanyuan
    Wu, Baoyindureng
    Wei, Ankang
    DISCRETE APPLIED MATHEMATICS, 2020, 285 (285) : 1 - 8
  • [49] Exact Analysis of k-Connectivity in Secure Sensor Networks with Unreliable Links
    Zhao, Jun
    Yagan, Osman
    Gligor, Virgil
    2015 13TH INTERNATIONAL SYMPOSIUM ON MODELING AND OPTIMIZATION IN MOBILE, AD HOC, AND WIRELESS NETWORKS (WIOPT), 2015, : 191 - 198
  • [50] Connectivity enhancement based on network coding for wireless multi-hop ad hoc networks
    Zhu X.
    Fang X.
    Xinan Jiaotong Daxue Xuebao/Journal of Southwest Jiaotong University, 2010, 45 (06): : 972 - 976
12345