能量均衡的最小连通支配集分布式算法  

Distributed Algorithm for Energy-Balance Minimum Connected Dominating Set

作　　者：凌飞[1] 吴振华[1] 

机构地区：[1]南昌航空大学软件学院,南昌330063

出　　处：《传感技术学报》2012年第9期1316-1321,共6页Chinese Journal of Sensors and Actuators

基　　金：国家自然科学基金项目(41101426);航空科学基金项目(2011ZD56004);江西省自然科学基金项目(2009GQS0086);江西省科技支撑计划重点项目(2010BGA02100)

摘　　要：在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。Minimum Connected Dominating Set（MCDS）mainly used for constructing virtual backbone in ad hoc network.Since virtual backbone usually plays an important role in ad hoc network and finding MCDS in an arbitrary graph is a NP-hard problem,many algorithms have been proposed to construct an approximation of MCDS.Most of them only consider the size of the dominating set but neglect the energy of nodes,which is not proper for wireless sensor network because of the strictly limited energy.When a low energy node is selected as a dominating node this node may consume all the energy quickly owing to the workload of dominating node.To address this shortcoming,we proposed a distributed algorithm for Energy-Balance Minimum Connected Dominating Set（EB-MCDS）.Two factors the degree and residuary energy of node have been considered to consist the dominating node election formulation in the EB-MCDS.Simulation results show that the EB-MCDS balanced energy consuming of network effectively and extend the network life cycle of about 20% compared with existing algorithms.

关 键 词：无线传感器网络 路由 能量均衡 最小连通支配集 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]