基于极小独立支配集的MANET虚拟骨干网算法

A Virtual Backbone Network Algorithm Based on a Minimal Independent Dominating Set for MANETs

对规模较大、移动较频繁的MANET(Mobile Ad hoc Networks),用独立支配集构建虚拟骨干网,克服骨干节点之间必须维护连通性的问题,使得拓扑变化较快时骨干网的重构能快速实现;利用极大独立集的求解得到极小独立支配集,并给出基于该支配集的虚拟骨干网数学模型及算法;通过仿真验证算法的有效性、低复杂度和自恢复能力.

Considering the characteristic of fast-moving inmobile ad hoc networks （MANETs） ,a virtual backbone network with a independent dominating set was constructed. This method can avoid sustaining connectivity between backbone nodes and the backbone network can be rapidly reconstructed as topology change. The minimal independent dominating set was settled by calculating maximal independent set, and with the set the algorithm and mathematical model of a virtual backbone network were provided. result shows that the algorithm bears efficiency,low complexity and self-recovering ability.