一种适用于单向ad-hoc网络的连通支配集算法  

An Energy Efficient Algorithm for Connected Dominating Set in Unidirectional Wireless Ad-Hoc Networks

作　　者：吴小燕[1] 聂欣[2] 朱艺华[1] 

机构地区：[1]浙江工业大学信息智能与决策优化研究所,杭州310014 [2]北京航空航天大学电子信息工程学院,北京100083

出　　处：《传感技术学报》2006年第3期905-907,925,共4页Chinese Journal of Sensors and Actuators

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

摘　　要：在ad-hoc网络中,基于最小连通支配集(minimumconnecteddominatingset---MCDS)的路由方法是一种有效的分层路由方法,它将路由搜索主要集中在连通支配集内。但目前提出的支配集算法大都是基于双向链路的,在网络中出现单向链路时无法正常工作。对此,本文重新定义了支配集概念,提出了一种适用于单向ad-hoc网络的最小连通支配集近似算法(UL-WMCDS),并给出了它的正确性。仿真表明,随着节点数目的增加和传输半径的增大,连通支配集所占的比例都逐渐减小。In wireless ad-hoc networks, routing based on connected dominating set is a promised approach, where the searching space for route is reduced to nodes in the dominating set. But most of the algorithms can＇t work well in unidirectional wireless ad-hoc networks. To the fact of the unidirectional links in wireless ad hoc networks we propose a maximal weighted algorithm for minimum connected dominating set. Also, we improve the correctness of the algorithm. Simulation results show that proposed approach can ensure the fewer nodes to form connected dominating set.

关 键 词：移动自组网 单向链路 支配集 网关 

分 类 号：TP212.9[自动化与计算机技术—检测技术与自动化装置] TN914[自动化与计算机技术—控制科学与工程]