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

Maximal Independent Set Based Distributed Algorithm for Minimum Connected Dominating Set

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是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.