Distributed Connected Dominating Set Algorithm to Enhance Connectivity of Wireless Nodes in Internet of Things Networks

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.