基于有界增长图的无线传感器网络虚拟骨干形成算法

Virtual backbone formation algorithm based on GBG for wireless sensor networks

提出了基于有界增长图的虚拟骨干近似形成算法(VBF)。算法采用网络划分机制构建极大独立集,使用染色过程形成簇图;以2分离集合子集递归计算(1+ε)近似局部最小支配集,合并局部最优解构造全局最优解;然后调整簇头传输范围直接以全局最优解形成最小近似连通支配集,无须加入网关节点,降低计算开销。构造的连通支配集具有常量扩展因子和常量度,并且算法运行时节点仅需直接邻域信息。理论分析和仿真比较证明了算法的正确性和有效性。

An approximation algorithm of virtual backbone formation （VBF） based on a more generalized and realistic wireless network communication model of bounded growth graph （GBG） was proposed. This approach constructs an maximal independent set （MIS） by network decomposition scheme and a clustergraph by coloring, computes local minimum dominating sets in 2-separated collection of subnets to form a global optimal solution which is used to directly construct an approximation minimum connected dominating sets by adjusting transmission range of clusterheads and finally use marking process and self-pruning to reduce the virtual backbone, without additional gateways. The computed connected dominating set guarantees a constant stretch factor and constant degree while the nodes only require direct neighborhood information. The efficiency and correctness of the VBF is confirmed through theoretical analysis as well as comparison study in details.