无线传感器网络最小覆盖集的贪婪近似算法

• 作者: 孙宏元 陆克中
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 无线传感器网络 网络生命期 节点调度 最小覆盖集 贪婪算法 近似算法
• 年，卷（期）: 2010,（10）
• 页码范围: 2656-2665
• 分类号: TP393
• 字数: 7748字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03670

摘要

网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陆克中	深圳大学计算机与软件学院	21	160	7.0	11.0