Maximal Independent Sets in Heterogeneous Wireless Ad Hoc Networks
Authors:
- 17 December 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 15 (8) , 2023-2033
Abstract
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.Keywords
Funding Information
- National Natural Science Foundation of China (61170005, 61170004, 61133011, 41304083)
This publication has 18 references indexed in Scilit:
- Minimum connected dominating set construction in wireless networks under the beeping model2015
- On connected domination in unit ball graphsOptimization Letters, 2010
- Connected Dominating Sets in Wireless Networks with Different Transmission RangesIEEE Transactions on Mobile Computing, 2007
- Minimum connected dominating sets and maximal independent sets in unit disk graphsTheoretical Computer Science, 2006
- The Densest Packing of 19 Congruent Circles in a CircleGeometriae Dedicata, 1999
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Densest packings of eleven congruent circles in a circleGeometriae Dedicata, 1994
- Unit Disk Graphs1991
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987
- Der Mindestabstand von n in der Einheitskreisscheibe gelegenen PunktenMathematische Nachrichten, 1969