摘要： 由于在无线传感器网络中通常使用虚拟骨干网来承担数据转发的任务，因此骨干节点的能量会过快地耗尽从而导致网络无法连通。针对该问题，提出一种基于连通坡面划分的多重虚拟骨干网轮换算法——MVBNR。算法利用图论中的连通坡面划分理论构造出尽可能多的无交集虚拟骨干网，使其周期性地轮流承担转发数据的任务，从而达到均衡网络负载、延长网络寿命的目的。理论分析表明，MVBNR算法构造了一个大小至少为[(δ+1)/(β×(c+1))]－f的连通坡面划分，算法的消息复杂度和时间复杂度都为O(nδ)。仿真结果表明，MVBNR算法产生的平均骨干节点数、骨干网络数和网络寿命都优于IDKDP算法。

关键词: 无线传感器网络, 连通坡面划分, 虚拟骨干网, 轮换, 负载均衡

Abstract: A virtual backbone network is used to take on forwarding data in Wireless Sensor Network(WSN), therefore the energy of these backbone nodes are run out too quickly, which causes the network not connected. To address this issue, this paper proposes a Multiple Virtual Backbone Networks Rotation(MVBNR) algorithm based on connected domatic partition. The algorithm uses the connected domatic partition of graph theory to construct as many disjoint virtual backbone networks as possible, let them periodically take turns forwarding data, so as to achieve the purpose of network load balancing and network lifetime extending. Theoretical analysis proves that the MVBNR algorithm constructs a connected domatic partition whose size is at least [(δ+1)/(β×(c+1))]－f and the algorithm’s message complexity and time complexity are O(nδ). Simulation result shows that the average number of backbone nodes, the number of backbone networks and the network lifetime produced by the MVBNR algorithm are better than those produced by the IDKDP algorithm.

Key words: Wireless Sensor Network(WSN), connected domatic partition, virtual backbone networks, rotation, load balancing

中图分类号: 

• TP393