基于极大独立集的最小连通支配集的分布式算法  

Maximal Independent Set Based Distributed Algorithm for Minimum Connected Dominating Set

作　　者：唐勇[1] 周明天[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都610054

出　　处：《电子学报》2007年第5期868-874,共7页Acta Electronica Sinica

基　　金：现代通信国家重点实验室基金(No.51436050203DZ0210);中国博士后科学研究基金(No.2005037114)

摘　　要：全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.Broadcasting is a basic operation in wireless sensor networks and mobile ad hoc networks. Reducing redundant retransmission nodes to save network resource is a critical problem for broadcasting.Minimizing retransmission nodes in broadcasting is equivalent to minimizing connected dominating set in graph theory, and finding a minimum connected dominating set is NP-complete for graphs.Based on maximal independent set,this paper proposes a distributed algorithm for minimum connected dominating set （MISB） ,and proves the accurateness of the algorithm. The simulation results show that,using this algorithm,the size of the resultant connected dominating set is smaller. So the algorithm can reduce the retransmission nodes and save network resources efficiently in broadcasting.

关 键 词：无线传感器网络 移动自组织网络 广播 极大独立集 最小连通支配集 

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