Minimum connected dominating set algorithms for ad hoc sensor networks

To achieve effective communication in ad hoc sensor networks, researchers have been working on finding a minimum connected dominating set (MCDS) as a virtual backbone network in practice. Presently, many approximate algorithms have been proposed to construct MCDS, the best among which is adopting th...

Full description

Saved in:
Bibliographic Details
Main Authors: Sun, Xuemei, Yang, Yongxin, Ma, Maode
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2019
Subjects:
Online Access:https://hdl.handle.net/10356/105969
http://hdl.handle.net/10220/48798
http://dx.doi.org/10.3390/s19081919
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-105969
record_format dspace
spelling sg-ntu-dr.10356-1059692019-12-06T22:01:51Z Minimum connected dominating set algorithms for ad hoc sensor networks Sun, Xuemei Yang, Yongxin Ma, Maode School of Electrical and Electronic Engineering Ad Hoc Sensor Networks DRNTU::Engineering::Electrical and electronic engineering Maximum Independent Set To achieve effective communication in ad hoc sensor networks, researchers have been working on finding a minimum connected dominating set (MCDS) as a virtual backbone network in practice. Presently, many approximate algorithms have been proposed to construct MCDS, the best among which is adopting the two-stage idea, that is, to construct a maximum independent set (MIS) firstly and then realize the connectivity through the Steiner tree construction algorithm. For the first stage, this paper proposes an improved collaborative coverage algorithm for solving maximum independent set (IC-MIS), which expands the selection of the dominating point from two-hop neighbor to three-hop neighbor. The coverage efficiency has been improved under the condition of complete coverage. For the second stage, this paper respectively proposes an improved Kruskal–Steiner tree construction algorithm (IK–ST) and a maximum leaf nodes Steiner tree construction algorithm (ML-ST), both of which can make the result closer to the optimal solution. Finally, the simulation results show that the algorithm proposed in this paper is a great improvement over the previous algorithm in optimizing the scale of the connected dominating set (CDS). Published version 2019-06-18T05:33:23Z 2019-12-06T22:01:51Z 2019-06-18T05:33:23Z 2019-12-06T22:01:51Z 2019 Journal Article Sun, X., Yang, Y., & Ma, M. (2019). Minimum connected dominating set algorithms for ad hoc sensor networks. Sensors, 19(8), 1919-. doi:10.3390/s19081919 1424-8220 https://hdl.handle.net/10356/105969 http://hdl.handle.net/10220/48798 http://dx.doi.org/10.3390/s19081919 en Sensors © 2019 The Authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). 15 p. application/pdf
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Ad Hoc Sensor Networks
DRNTU::Engineering::Electrical and electronic engineering
Maximum Independent Set
spellingShingle Ad Hoc Sensor Networks
DRNTU::Engineering::Electrical and electronic engineering
Maximum Independent Set
Sun, Xuemei
Yang, Yongxin
Ma, Maode
Minimum connected dominating set algorithms for ad hoc sensor networks
description To achieve effective communication in ad hoc sensor networks, researchers have been working on finding a minimum connected dominating set (MCDS) as a virtual backbone network in practice. Presently, many approximate algorithms have been proposed to construct MCDS, the best among which is adopting the two-stage idea, that is, to construct a maximum independent set (MIS) firstly and then realize the connectivity through the Steiner tree construction algorithm. For the first stage, this paper proposes an improved collaborative coverage algorithm for solving maximum independent set (IC-MIS), which expands the selection of the dominating point from two-hop neighbor to three-hop neighbor. The coverage efficiency has been improved under the condition of complete coverage. For the second stage, this paper respectively proposes an improved Kruskal–Steiner tree construction algorithm (IK–ST) and a maximum leaf nodes Steiner tree construction algorithm (ML-ST), both of which can make the result closer to the optimal solution. Finally, the simulation results show that the algorithm proposed in this paper is a great improvement over the previous algorithm in optimizing the scale of the connected dominating set (CDS).
author2 School of Electrical and Electronic Engineering
author_facet School of Electrical and Electronic Engineering
Sun, Xuemei
Yang, Yongxin
Ma, Maode
format Article
author Sun, Xuemei
Yang, Yongxin
Ma, Maode
author_sort Sun, Xuemei
title Minimum connected dominating set algorithms for ad hoc sensor networks
title_short Minimum connected dominating set algorithms for ad hoc sensor networks
title_full Minimum connected dominating set algorithms for ad hoc sensor networks
title_fullStr Minimum connected dominating set algorithms for ad hoc sensor networks
title_full_unstemmed Minimum connected dominating set algorithms for ad hoc sensor networks
title_sort minimum connected dominating set algorithms for ad hoc sensor networks
publishDate 2019
url https://hdl.handle.net/10356/105969
http://hdl.handle.net/10220/48798
http://dx.doi.org/10.3390/s19081919
_version_ 1681036120931958784