On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks
Joint Authors
Liang, Jiarong
Yi, Meng
Zhang, Weiguang
Li, Yanyan
Liang, Xinyu
Qin, Bin
Source
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-12, 12 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-02-24
Country of Publication
Egypt
No. of Pages
12
Main Subjects
Abstract EN
In a wireless ad hoc network, the size of the virtual backbone (VB) is an important factor for measuring the quality of the VB.
The smaller the VB is, the less the overhead caused by the VB.
Since ball graphs (BGs) have been used to model 3-dimensional wireless ad hoc networks and since a connected dominating set can be used to represent a VB undertaking routing-related tasks, the problem of finding the smallest VB is transformed into the problem of finding a minimum connected dominating set (MCDS).
Many research results on the MCDS problem have been obtained for unit disk graphs and unit ball graphs, in which the transmission ranges of all nodes are identical.
In some situations, the node powers can vary.
One can model such a network as a graph with different transmission ranges for different nodes.
In this paper, we focus on the problem of minimum strongly connected dominating and absorbing sets (MSCDASs) in a strongly connected directed ball graph with different transmission ranges, which is also NP-hard.
We design an algorithm considering the construction of a strongly connected dominating and absorbing set (SCDAS), whose size does not exceed 319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15, where opt is the size of an MCDAS and k denotes the ratio of rmax to rmin in the ad hoc network with transmission range rmin,rmax.
Our simulations show the feasibility of the algorithm proposed in this paper.
American Psychological Association (APA)
Liang, Jiarong& Yi, Meng& Zhang, Weiguang& Li, Yanyan& Liang, Xinyu& Qin, Bin. 2020. On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks. Complexity،Vol. 2020, no. 2020, pp.1-12.
https://search.emarefa.net/detail/BIM-1145442
Modern Language Association (MLA)
Li, Yanyan…[et al.]. On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks. Complexity No. 2020 (2020), pp.1-12.
https://search.emarefa.net/detail/BIM-1145442
American Medical Association (AMA)
Liang, Jiarong& Yi, Meng& Zhang, Weiguang& Li, Yanyan& Liang, Xinyu& Qin, Bin. On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks. Complexity. 2020. Vol. 2020, no. 2020, pp.1-12.
https://search.emarefa.net/detail/BIM-1145442
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1145442