To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints i...To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.展开更多
In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided ...In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided into three phases: 1) Area Partition; 2) Area Expansion; 3) Area Connection. In additional, maintenance strategy is proposed in each phase respectively to handle node mobility with timer. At last, the simulation is implemented with OPNET and MATLAB and the results are analyzed in detailed with Size of CDS, Message Overhead and other indexes.展开更多
This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connec...This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connectivity and efficiency of the CDS. Compared with Wu's algorithm, the proposed algorithm can make full use of present network conditions and involves fewer nodes. Also it has better performance with regard to the approximation factor, message complexity, and time complexity.展开更多
Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if i...Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if its neighbors with larger keys cannot cover it together.Then a simple distributed CDS construction algorithm is proposed, which is more effective than the existing algorithms in reducing the dominating set size and the computation complexity at the same time. Simulation results also confirm this, especially in relatively dense networks.展开更多
The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that...The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .展开更多
Clustering or connected dominating set (CDS) both approaches can establish a virtual backbone (VB) in wireless sensor networks (WSNs) or wireless mesh networks (WMNs). Each cluster consisting of a cluster head (CH) an...Clustering or connected dominating set (CDS) both approaches can establish a virtual backbone (VB) in wireless sensor networks (WSNs) or wireless mesh networks (WMNs). Each cluster consisting of a cluster head (CH) and its neighboring nodes can form a dominating set. After some bridging nodes were selected, cluster heads (CHs) connected through these bridging nodes naturally formed a CDS. Although CDS provides obvious backbone architecture, however, the number of cluster heads and bridging nodes may be too large, this may cause the loss of advantages of virtual backbone. When we effectively reduce their numbers, more effectively WCDS (Weakly Connected Dominating Set) can be fining out. Some essential topics on constructing WCDS-based VB in WSN/WMN are discussed in this paper. From the point of view of three different protocol layers, including network (NWK) layer, MAC layer, and physical (PHY) layer, we explore their cross-layer research topics and design algorithms. For NWK layer, area-based WCDS algorithms and routing strategies including via VB and not via VB are discussed. For MAC layer, a WCDS-based energy-efficient MAC protocol is presented. For PHY layer, battery-aware alternative VB selections and sensor nodes with different transmission ranges are addressed.展开更多
基金Major Program of the National Natural Science Foundation of China (No.70533050)High Technology Research Program ofJiangsu Province(No.BG2007012)+1 种基金China Postdoctoral Science Foundation(No.20070411065)Science Foundation of China University of Mining andTechnology(No.OC080303)
文摘To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.
基金supported by the National Science and Technology Support Program of China (2015BAG10B01)the Science and Technology Project of State Grid Corporation of China (SGIT0000KJJS1500008)
文摘In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided into three phases: 1) Area Partition; 2) Area Expansion; 3) Area Connection. In additional, maintenance strategy is proposed in each phase respectively to handle node mobility with timer. At last, the simulation is implemented with OPNET and MATLAB and the results are analyzed in detailed with Size of CDS, Message Overhead and other indexes.
文摘This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connectivity and efficiency of the CDS. Compared with Wu's algorithm, the proposed algorithm can make full use of present network conditions and involves fewer nodes. Also it has better performance with regard to the approximation factor, message complexity, and time complexity.
基金Supported by the National Natural Science Foundation of China (No.60202005).
文摘Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if its neighbors with larger keys cannot cover it together.Then a simple distributed CDS construction algorithm is proposed, which is more effective than the existing algorithms in reducing the dominating set size and the computation complexity at the same time. Simulation results also confirm this, especially in relatively dense networks.
文摘The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .
文摘Clustering or connected dominating set (CDS) both approaches can establish a virtual backbone (VB) in wireless sensor networks (WSNs) or wireless mesh networks (WMNs). Each cluster consisting of a cluster head (CH) and its neighboring nodes can form a dominating set. After some bridging nodes were selected, cluster heads (CHs) connected through these bridging nodes naturally formed a CDS. Although CDS provides obvious backbone architecture, however, the number of cluster heads and bridging nodes may be too large, this may cause the loss of advantages of virtual backbone. When we effectively reduce their numbers, more effectively WCDS (Weakly Connected Dominating Set) can be fining out. Some essential topics on constructing WCDS-based VB in WSN/WMN are discussed in this paper. From the point of view of three different protocol layers, including network (NWK) layer, MAC layer, and physical (PHY) layer, we explore their cross-layer research topics and design algorithms. For NWK layer, area-based WCDS algorithms and routing strategies including via VB and not via VB are discussed. For MAC layer, a WCDS-based energy-efficient MAC protocol is presented. For PHY layer, battery-aware alternative VB selections and sensor nodes with different transmission ranges are addressed.
