无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

An Energy-Balanced Connected Dominating Sets for Data Gatheringin Wireless Sensor Networks

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.

Connected Dominating Sets（CDS） has been proposed as the virtual backbone to alleviate the broadcasting storm problem and perform some other tasks such as data gathering in wireless sensor networks.Many previous researches mainly focus on how to construct a small virtual backbone for high efficient data gathering,which is modeled as the Minimum Connected Dominating Set（MCDS） problem.However,the MCDS cannot balance the energy consumptions among nodes,which shorten the network lifetime.Therefore,it is desirable to construct an energy-balanced CDS.In this paper,a novel distributed schema,called EBCDS（Energy-Balanced Connected Dominating Sets） algorithm is proposed to balance the energy consumption of the network and enlarge the network lifetime.In EBCDS,each node in the CDS has high energy and large degree,and these nodes form a virtual backbone in the network.By transmitting data through the backbone with small routing space,each node can preserve its energy effectively.Moreover,the nodes in the backbone would not die quickly because of lacking of energy.Theoretical analyses show that EBCDS can construct a CDS with O（nlogn） message complexity,and simulations results prove the efficiency of the proposed algorithm in terms of energy consumption and network lifetime.