On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks
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...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/9189645 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552095297830912 |
|---|---|
| author | Jiarong Liang Meng Yi Weiguang Zhang Yanyan Li Xinyu Liang Bin Qin |
| author_facet | Jiarong Liang Meng Yi Weiguang Zhang Yanyan Li Xinyu Liang Bin Qin |
| author_sort | Jiarong Liang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-bf0520b173db4527bddcb37655331b3d |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-bf0520b173db4527bddcb37655331b3d2025-02-03T05:59:35ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/91896459189645On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc NetworksJiarong Liang0Meng Yi1Weiguang Zhang2Yanyan Li3Xinyu Liang4Bin Qin5School of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaSchool of Computer, Electronics and Information, Guangxi University, Nanning 530004, ChinaIn 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.http://dx.doi.org/10.1155/2020/9189645 |
| spellingShingle | Jiarong Liang Meng Yi Weiguang Zhang Yanyan Li Xinyu Liang Bin Qin On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks Complexity |
| title | On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks |
| title_full | On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks |
| title_fullStr | On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks |
| title_full_unstemmed | On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks |
| title_short | On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks |
| title_sort | on constructing strongly connected dominating and absorbing set in 3 dimensional wireless ad hoc networks |
| url | http://dx.doi.org/10.1155/2020/9189645 |
| work_keys_str_mv | AT jiarongliang onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks AT mengyi onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks AT weiguangzhang onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks AT yanyanli onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks AT xinyuliang onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks AT binqin onconstructingstronglyconnecteddominatingandabsorbingsetin3dimensionalwirelessadhocnetworks |