Maximal Independent Sets in Heterogeneous Wireless Ad Hoc Networks

被引:15
作者
Bai, Sen [1 ]
Che, Xiangjiu [1 ]
Bai, Xin [1 ]
Wei, Xiaohui [1 ]
机构
[1] Jilin Univ, Coll Comp Sci & Technol, Key Lab Symbol Computat & Knowledge Engn, Minist Educ, Changchun, Jilin, Peoples R China
基金
中国国家自然科学基金;
关键词
Heterogeneous wireless ad hoc network; connected dominating set; maximal independent set; disk graphs with bidirectional links; ball graphs with bidirectional links; CONNECTED DOMINATING SETS; CONGRUENT CIRCLES; PACKINGS;
D O I
10.1109/TMC.2015.2508805
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In ad hoc wireless networks, a Connected Dominating Set (CDS) has been extensively used as a Virtual Backbone (VB) for routing. The majority of approximation algorithms for constructing a small CDS in wireless ad hoc networks follow a general two-phased approach. The first phase is to construct a Dominating Set (DS) and the second phase is to connect the nodes in it. Generally, in the first phase, a Maximum Independent Set (MIS) is used as the DS. The relation between the size of a Maximum Independent Set and a Minimum Connected Dominating Set (MCDS) plays the key role in the performance analyses of these two-phased algorithms. In homogeneous wireless ad hoc networks modeled as Unit Disk Graphs (UDG) and Unit Ball Graphs (UBG), the relation between them has been well studied. However, in heterogeneous wireless networks which generally modeled as Disk Graphs with Bidirectional links (DGB) and Ball Graphs with Bidirectional links (BGB), upper bounds for the size of MISs have seldom been studied. In this paper, we give tighter upper bounds for the size of MISs in heterogeneous wireless ad hoc networks. When the maximum and minimum transmission range are relatively close, our result is much better. In DGB, when the transmission range ratio is (1,1.152], (1.152,1.307], (1.307,1.407], (1.407,1.462], (1.462,1.515], (1.515,1.618], (1.618,1.932], we prove that the size of any Maximal Independent Set (MIS) is upper bounded by 6opt + 1, 7opt + 1, 8opt + 1, 9opt + 1, 10opt + 1, 11opt + 1, 16.7778opt + 1.2222, where opt denotes the size of an optimal solution of the CDS problem.
引用
收藏
页码:2023 / 2033
页数:11
相关论文
共 50 条
[21]   Distributed construction of connected dominating set in wireless ad hoc networks [J].
Wan, PJ ;
Alzoubi, KM ;
Frieder, O .
MOBILE NETWORKS & APPLICATIONS, 2004, 9 (02) :141-149
[22]   Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks [J].
Peng-Jun Wan ;
Khaled M. Alzoubi ;
Ophir Frieder .
Mobile Networks and Applications, 2004, 9 :141-149
[23]   Lower Bounds for Maximal Matchings and Maximal Independent Sets [J].
Balliu, Alkida ;
Brandt, Sebastian ;
Hirvonen, Juho ;
Olivetti, Dennis ;
Rabie, Mikael ;
Suomela, Jukka .
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, :481-497
[24]   Lower Bounds for Maximal Matchings and Maximal Independent Sets [J].
Balliu, Alkida ;
Brandt, Sebastian ;
Hirvonen, Juho ;
Olivetti, Dennis ;
Rabie, Mikael ;
Suomela, Jukka .
JOURNAL OF THE ACM, 2021, 68 (05)
[25]   Maximal independent sets in minimum colorings [J].
Arumugam, S. ;
Haynes, Teresa W. ;
Henning, Michael A. ;
Nigussie, Yared .
DISCRETE MATHEMATICS, 2011, 311 (13) :1158-1163
[26]   Maximal independent sets on a grid graph [J].
Oh, Seungsang .
DISCRETE MATHEMATICS, 2017, 340 (12) :2762-2768
[27]   Maximal independent sets in grid graphs [J].
Ortiz, Carmen ;
Villanueva, Monica .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2017, 24 (1-2) :369-385
[28]   Polar graphs and maximal independent sets [J].
Lozin, Vadim V. ;
Mosca, Raffaele .
DISCRETE MATHEMATICS, 2006, 306 (22) :2901-2908
[29]   Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of Transmissions [J].
Khabbazian, Majid ;
Blake, Ian F. ;
Bhargava, Vijay K. .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2012, 11 (03) :402-413
[30]   Performance Analysis and Enhancement for Backbone Based Wireless Mobile Ad Hoc Networks [J].
Ju, Huei-jiun ;
Rubin, Izhak .
2ND INTERNATIONAL CONFERENCE ON BROADBAND NETWORKS (BROADNETS 2005), 2005, :789-798