Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/105969
Title: Minimum connected dominating set algorithms for ad hoc sensor networks
Authors: Sun, Xuemei
Yang, Yongxin
Ma, Maode
Keywords: Ad Hoc Sensor Networks
DRNTU::Engineering::Electrical and electronic engineering
Maximum Independent Set
Issue Date: 2019
Source: 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
Series/Report no.: Sensors
Abstract: 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).
URI: https://hdl.handle.net/10356/105969
http://hdl.handle.net/10220/48798
ISSN: 1424-8220
DOI: 10.3390/s19081919
Rights: © 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/).
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:EEE Journal Articles

Files in This Item:
File Description SizeFormat 
Minimum connected dominating set algorithms for ad hoc sensor networks.pdf3.32 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

1
Updated on Jul 16, 2020

PublonsTM
Citations 50

1
Updated on Mar 4, 2021

Page view(s)

159
Updated on May 28, 2022

Download(s) 50

23
Updated on May 28, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.