图的正面影响控制集中贪婪算法的设计与分析

摘要:

对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.

It is necessary to design good and reasonable topology protocol to prolong the lifetime of sensor nodes and the whole network.According to the chart control set in the application of wireless sensor network to form a virtual backbone network,we studies positive influence dominating set problem in graph,which is a variant of dominating set problem in graph.We divide the problem into two cases according to whether there are isolated vertices in graph,then design greedy algorithms and analyze performance ratios respectively.

作者:

张涛 朱莉娟

机构地区:

新乡学院网络管理中心 新乡学院计算机与信息工程学院

出处:

《betway官方app 学报：自然科学版》 CAS 北大核心 2015年第2期169-172,共4页

基金:

河南省重点科技攻关项目(092102210149)

关键词:

无线传感器网络 图 控制集 贪婪算法 性能比

wireless sensor network graph dominating set greedy algorithm performance ratio

分类号:

TP393 [自动化与计算机技术—计算机应用技术]

图的正面影响控制集中贪婪算法的设计与分析.pdf