Distributed Connected Dominating Set Algorithm to Enhance Connectivity of Wireless Nodes in Internet of Things Networks
Dina S. M. Hassan*, Reem Ibrahim Alkanhel, Thuraya Alrumaih, Shiyam Alalmaei
Department of Information Technology, College of Computer and Information Sciences, Princess Nourah bint Abdulrahman University, P.O. Box 84428, Riyadh, Saudi Arabia
* Corresponding Author: Dina S. M. Hassan. Email: 
Computers, Materials & Continua https://doi.org/10.32604/cmc.2026.074751
Received 17 October 2025; Accepted 06 January 2026; Published online 28 January 2026
Abstract
The sustainability of the Internet of Things (IoT) involves various issues, such as poor connectivity, scalability problems, interoperability issues, and energy inefficiency. Although the Sixth Generation of mobile networks (6G) allows for Ultra-Reliable Low-Latency Communication (URLLC), enhanced Mobile Broadband (eMBB), and massive Machine-Type Communications (mMTC) services, it faces deployment challenges such as the short range of sub-THz and THz frequency bands, low capability to penetrate obstacles, and very high path loss. This paper presents a network architecture to enhance the connectivity of wireless IoT mesh networks that employ both 6G and Wi-Fi technologies. In this architecture, local communications are carried through the mesh network, which uses a virtual backbone to relay packets to local nodes, while remote communications are carried through the 6G network. The virtual backbone is created using a heuristic distributed Connected Dominating Set (CDS) algorithm. In this algorithm, each node uses information collected from its one- and two-hop neighbors to determine its role and find the set of expansion nodes that are used to select the next CDS nodes. The proposed algorithm has
O(n) message and
O(K) time complexities, where
n is the number of nodes in the network, and
K is the depth of the cluster. The study proved that the approximation ratio of the algorithm has an upper bound of
2.06748 (3.4306 MCDS + 4.8185). Performance evaluations compared the size of the CDS against the theoretical limit and recent CDS clustering algorithms. Results indicate that the proposed algorithm has the smallest average slope for the size of the CDS as the number of nodes increases.
Keywords
Connected dominating sets; CDS; virtual backbone; unit disk graph; UDG; mIoT; multi-RAT
Open Access
Login
Register
Submit a Paper
Propose a Special lssue
Download PDF
Downloads
Citation Tools
