YANG Mingxia，WANG Wanliang，MA Chenming（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 34000，China；.College of Information，Zhejiang University of Technology，Hangzhou 31003，China）



Energy Balanced and Fault Tolerant Data Gathering Algorithm
for Heterogeneous Wireless Sensor Network*

YANG Mingxia1，2，WANG Wanliang2*，MA Chenming2
（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 324000，China；2.College of Information，Zhejiang University of Technology，Hangzhou 310023，China）

Virtual backbone based on connected dominating setcan prolong the lifetime of wireless sensor network. However，the network also needs to have a certain degree of fault tolerance due to characteristicsof the nodes that are prone to failure.In view of the problem that the fault tolerant methods of k-connected m-dominated set consume too much energy，a distributed data gathering algorithm for energy-saving and fault-tolerance is proposed in the new⁃ly heterogeneous network mode.The algorithm firstly construct connected dominating set，then select better degree of fault tolerance nodes as backup nodes，and finally balance the energy consumption of the dominated nodes in the data gathering process.Theoretical analysisand simulation experimentsconfirm that our algorithm not only can con⁃struct connected dominating set with low time and message overhead，but also ensure the fault tolerance and extend the network lifetime finally.

heterogeneous wireless sensornetwork；connected dominating set；data gathering；fault tolerant；load balance

随着物联网技术的快速发展，数据已经成为社会发展的核心内容。作为末端采集系统，无线传感器网络（Wireless Sensor Networks，WSNs）可以实现物理世界与信息世界的有效融合。资源受限导致传感器网络在部署规模和运行时间等方面存在大量难题和挑战。利用节点的空间冗余性，可利用网络中部分节点工作来节省能耗，这类方法最典型的做法是拓扑控制，通过优化网络的拓扑结构，使得网络中节点的能耗均衡，延长网络生命时间。

其中，基于虚拟骨干的拓扑控制方法［1-4］通过求解一个确保网络连通的连通支配集，覆盖网络中所有其它非骨干节点，目标函数是减少工作节点规模。采用连通支配集作为虚拟骨干可以有效减少活跃节点数和路由开销，同时对于节点的管理和维护也更加容易，是一种有效的节能方法。但是，在实际环境中可能会出现节点死亡和链路错误等问题。

本文主要从节能和容错两个方面对无线传感器网络的能量节省问题进行研究，针对异构网络模型研究分布式容错数据收集算法，通过对活跃节点产生备份集的方法来生成容错拓扑，减少处于工作的支配节点数，从而节省网络能量，维持网络的稳定性。

1　相关研究工作

虚拟骨干网可以利用图论中求解最小连通支配集（Minimum Connected Dominating Set，MCDS）问题的方法来构建。现有算法可以分为减少能耗和保证高可靠性。

EBCDS［5］通过选择能量水平和度均比较大的节点组成连通支配集，支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干。……