基于极大权的最小连通支配集启发式算法  

A Heuristic Algorithm for Minimum Connected Dominating Set with Maximal Weight in Ad Hoc Networks

作　　者：阎新芳[1] 孙雨耕[1] 胡华东[1] 

机构地区：[1]天津大学电气与自动化工程学院

出　　处：《电子学报》2004年第11期1774-1777,共4页Acta Electronica Sinica

基　　金：教育部博士学科点基金 (No.2 0 0 30 0 560 0 7)

摘　　要：Adhoc无线网络中基于最小连通支配集 (MCDS)的路由是一个引人瞩目的方法 ,文中提出了一种基于极大权的MCDS的启发式算法 ,确保了性能强的主机担任网关节点的角色 ,能更好的协调管理网络中其他的节点 ,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础 .仿真结果表明 ,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性 。Routing based on a minimum connected dominating set (MCDS) in ad hoc wireless networks is a promising approach,where the search space for a route is reduced to nodes in the set (also called gateway nodes).This paper introduces MWMCDS,a simple and efficient heuristic algorithm for calculating minimum connected dominating set with maximal weight in the topology graph G of an Ad hoc wireless network.The maximality of the weight-based choice of gateway nodes guarantees that the most suitable nodes have been chosen for the role of gateway nodes so that they can properly coordinate all the other nodes in the network.As a result,it can keep stability of the MCDS and provide a highly effective communication base for broadcast and routing operation in the whole network.Simulation resluts show that the proposed algorithm can ensure the maximality of sum of CDS' weight and the minimality of CDS' size.So the scheme can be potentially used in designing efficient routing algorithms based on a MCDS.

关 键 词：AD HOC网络 极大权最小连通支配集 网关节点 启发式算法 广播 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]