The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless netwo...The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless networks. The quality of a virtual backbone is measured not only by approximation factor, which is the ratio of its size to that of minimum CDS, but also time complexity and message complexity. In this paper, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor networks. By destroying triangular loops in the virtual backbone, the proposed algorithm can effectively construct a CDS with smaller size. Moreover, our algorithm, which is fully localized, has a constant approximation ratio, linear message and time complexity, and low implementation complexity. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches.展开更多
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.展开更多
This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Consider...This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a hostaffects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.展开更多
基金The National Natural Science Foundation ofChina(No.60272082)The Important Science and Technology Key Item of Shanghai(No.05dzl5004)
文摘The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless networks. The quality of a virtual backbone is measured not only by approximation factor, which is the ratio of its size to that of minimum CDS, but also time complexity and message complexity. In this paper, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor networks. By destroying triangular loops in the virtual backbone, the proposed algorithm can effectively construct a CDS with smaller size. Moreover, our algorithm, which is fully localized, has a constant approximation ratio, linear message and time complexity, and low implementation complexity. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches.
基金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.
基金Supported by National Natural Science Foundation of China (No.60973141)Natural Science Foundation of Tianjin (No.09JCYBJC00300)
文摘This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a hostaffects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.
