The connected dominating set(CDS)problem,which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs(UDGs).This paper focuses on the CDS problem in wireless n...The connected dominating set(CDS)problem,which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs(UDGs).This paper focuses on the CDS problem in wireless networks.Investigation of some properties of independent set(IS)in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms.Several constant factor approximation algorithms are presented for the CDS problem in UDGs.Simulation results show that the proposed algorithms perform better than some known ones.展开更多
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(...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 ConnectedDominating 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 algorithmhas an upper bound of 2.06748(3.4306MCDS+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.展开更多
基金supported by the National Natural Science Foundation of China under Grant No 60473090the National"11th Five-Year-Supporting-Plan"of China under Grant No 2006BAH02A0407
文摘The connected dominating set(CDS)problem,which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs(UDGs).This paper focuses on the CDS problem in wireless networks.Investigation of some properties of independent set(IS)in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms.Several constant factor approximation algorithms are presented for the CDS problem in UDGs.Simulation results show that the proposed algorithms perform better than some known ones.
基金Deputyship for Research&Innovation,Ministry of Education in Saudi Arabia for funding this research work through the project number RI-44-0028.
文摘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 ConnectedDominating 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 algorithmhas an upper bound of 2.06748(3.4306MCDS+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.
