抑制 Delaunay triangulated 不规则的网络是在地球科学使用的一个种动态数据结构。关于在 CD 听的点和边插入的研究是它的申请的基础。与点和抑制的边插入的算法作比较，有很关于在 CD 听的抑制的边删除的一些研究。基于抑制的边的多...抑制 Delaunay triangulated 不规则的网络是在地球科学使用的一个种动态数据结构。关于在 CD 听的点和边插入的研究是它的申请的基础。与点和抑制的边插入的算法作比较，有很关于在 CD 听的抑制的边删除的一些研究。基于抑制的边的多型性的分析，虚拟点被用来描述抑制的边的交叉。一个新算法被介绍，作为影响领域 retriangulating 要求了虚拟点(IDRVP ) ，与虚拟点抑制了边删除。算法在拓扑学是完全的。最后，算法被一些应用盒子测试。展开更多
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 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.
