一种基于AVBR的计算CDS的改进算法  

An Improved Algorithm for Computing CDS Based on AVBR

作　　者：金伟民[1] 程胜[1] 武穆清[1] 丁炜[1] 

机构地区：[1]北京邮电大学北邮-Intel互联网交换架构实验室,北京100876

出　　处：《计算机工程》2005年第14期64-66,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60372101)

摘　　要：在WuandLi算法的基础上,提出了一种有限状态机模型。利用有限状态机的状态转移、节点的颜色标记和消息的发送和接收机制,建立了可靠的并行模型,实现节点的颜色标记过程与冗余节点的删除过程的融合。算法使用新的缩减规则,减少生成的主节点数,提高了算法的性能。This article presents a finite state machine based on Wu and Li’s algorithms. With the node color labeling and messagesending-receiving mechanism,it constructs a distributed and parallel model, and realizes the amalgamation of the marking process and the reducingprocess. With the new rules of reducing node,the amount of nodes in CDS is decreased and the approximation factor of the algorithm is improved.

关 键 词：AD HOC 无线网络 虚拟骨干 连接主节点集 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]