In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected domi...In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network.展开更多
基金supported partially by the science and technology project of CQ CSTC(No.cstc2012jjA40037)
文摘In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network.
