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 条
[41]   Maximal independent sets in a generalisation of caterpillar graph [J].
K. S. Neethi ;
Sanjeev Saxena .
Journal of Combinatorial Optimization, 2017, 33 :326-332
[42]   The Maximal 2-independent Sets in Trees [J].
Jou, Min-Jen ;
Lin, Jenq-Jong .
PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON APPLIED MATHEMATICS, SIMULATION AND MODELLING, 2016, 41 :106-109
[43]   Maximal independent sets in complementary prism graphs [J].
Barbosa, Rommel M. ;
Cappelle, Marcia R. ;
Coelho, Erika M. M. .
ARS COMBINATORIA, 2018, 137 :283-294
[44]   A representation diagram for maximal independent sets of a graph [J].
Taki, M ;
Masuda, S ;
Kashiwabara, T .
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1998, E81A (05) :784-788
[45]   On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad Hoc Networks [J].
Sheu, Pi-Rong ;
Tsai, Hung-Yuan ;
Lee, Ying-Po ;
Cheng, Jyun-Yan .
JOURNAL OF APPLIED SCIENCE AND ENGINEERING, 2009, 12 (04) :417-428
[46]   Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets [J].
Assadi, Sepehr ;
Kol, Gillat ;
Oshman, Rotem .
PROCEEDINGS OF THE 39TH SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2020, 2020, :79-88
[47]   Minimum-Transmission Broadcast in Uncoordinated Duty-Cycled Wireless Ad Hoc Networks [J].
Hong, Jue ;
Cao, Jiannong ;
Li, Wenzhong ;
Lu, Sanglu ;
Chen, Daoxu .
IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 2010, 59 (01) :307-318
[48]   A Contention Aware Connected Dominating Set Construction Algorithm for Wireless Ad-Hoc Networks [J].
Ferdous, Chowdhury Nawrin ;
Rahman, Ashikur .
2018 14TH INTERNATIONAL CONFERENCE ON WIRELESS AND MOBILE COMPUTING, NETWORKING AND COMMUNICATIONS (WIMOB 2018), 2018,
[49]   An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata [J].
Torkestani, Jayad Akbari ;
Meybodi, Mohammad Reza .
COMPUTER NETWORKS, 2010, 54 (05) :826-843
[50]   A New Local Algorithm for Backbone Formation in Ad Hoc Networks [J].
Kassaei, Hossein ;
Mehrandish, Mona ;
Narayanan, Lata ;
Opatrny, Jaroslav .
PE-WASUN09: PROCEEDINGS OF THE SIXTH ACM INTERNATIONAL SYMPOSIUM ON PERFORMANCE EVALUATION OF WIRELESS AD-HOC, SENSOR, AND UBIQUITOUS NETWORKS, 2009, :49-57