Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to larg...Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to large networks. This paper presents the Ad Hoc Broadcast Protocol (AHBP) and its performance is discussed. In the protocol, messages are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network. AHBP can efficiently reduce the redundant messages which make flooding-like protocols perform badly in large dense networks. Simulations are conducted to determine the performance characteristics of the protocol. The simulation results have shown excellent reduction of broadcast redundancy with AHBP. It also contributes to a reduced level of broadcast collision and congestion.展开更多
自组网以灵活的组网特性正越来越受到人们的关注。然而,这种灵活特性又给自组网的安全性带来了巨大的挑战。密钥管理是实现该类网络安全的重要环节。首先,基于补图团的着色思想提出了分布式分簇算法,在此基础上,结合TGDH(Tree-Based Gro...自组网以灵活的组网特性正越来越受到人们的关注。然而,这种灵活特性又给自组网的安全性带来了巨大的挑战。密钥管理是实现该类网络安全的重要环节。首先,基于补图团的着色思想提出了分布式分簇算法,在此基础上,结合TGDH(Tree-Based Group D iffie-Hellman)算法给出了一种混合密钥管理方案。理论分析此方案具有良好的性能。展开更多
Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected ...Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected m-Dominating Set （（k,m）-CDS） in a network as a fault-tolerant virtual backbone to help the routing process, which will save the energy of non-dominators and improve the network performance significantly. Considering the economic cost and efficiency, we choose （2,m）-CDS as the object of this paper, which is helpful enough in practical applications and has a smaller size. We firstly study the existing algorithms for （k,m）- CDS and figure out the problems of these designs. Then we propose a new distributed algorithm named Dominating Set Based AIgorithm （DSBA） with three sub-routines： Dominating Set AIgorithm （DSA）, Connection Algorithm （CA）, and Connectivity Expansion Algorithm （CEA）. Instead of commonly used Maximal Independent Set （MIS）, we pick dominating set directly from the given graph, and then connect them by a two-step ring based connecting strategy to satisfy the 2-connectivity. We also provide the correctness and complexity analysis of DSBA. At last, we compare DSBA with the last construction Distributed Deterministic Algorithm （DDA） by several numerical experiments. The simulation results show that DSBA improves over 30 percent of the performance of DDA, proving that DSBA is more practical for real-world applications.展开更多
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 .展开更多
基金the National '863' High-Tech Programme of China (No. 863- 300- 01-03-99 ).
文摘Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to large networks. This paper presents the Ad Hoc Broadcast Protocol (AHBP) and its performance is discussed. In the protocol, messages are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network. AHBP can efficiently reduce the redundant messages which make flooding-like protocols perform badly in large dense networks. Simulations are conducted to determine the performance characteristics of the protocol. The simulation results have shown excellent reduction of broadcast redundancy with AHBP. It also contributes to a reduced level of broadcast collision and congestion.
文摘自组网以灵活的组网特性正越来越受到人们的关注。然而,这种灵活特性又给自组网的安全性带来了巨大的挑战。密钥管理是实现该类网络安全的重要环节。首先,基于补图团的着色思想提出了分布式分簇算法,在此基础上,结合TGDH(Tree-Based Group D iffie-Hellman)算法给出了一种混合密钥管理方案。理论分析此方案具有良好的性能。
基金Supported by the National Natural Science Foundation of China (Nos. 61033002 and 61202024)
文摘Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected m-Dominating Set （（k,m）-CDS） in a network as a fault-tolerant virtual backbone to help the routing process, which will save the energy of non-dominators and improve the network performance significantly. Considering the economic cost and efficiency, we choose （2,m）-CDS as the object of this paper, which is helpful enough in practical applications and has a smaller size. We firstly study the existing algorithms for （k,m）- CDS and figure out the problems of these designs. Then we propose a new distributed algorithm named Dominating Set Based AIgorithm （DSBA） with three sub-routines： Dominating Set AIgorithm （DSA）, Connection Algorithm （CA）, and Connectivity Expansion Algorithm （CEA）. Instead of commonly used Maximal Independent Set （MIS）, we pick dominating set directly from the given graph, and then connect them by a two-step ring based connecting strategy to satisfy the 2-connectivity. We also provide the correctness and complexity analysis of DSBA. At last, we compare DSBA with the last construction Distributed Deterministic Algorithm （DDA） by several numerical experiments. The simulation results show that DSBA improves over 30 percent of the performance of DDA, proving that DSBA is more practical for real-world applications.
文摘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 .
