基于传感器移动距离最小化的路径覆盖算法
来源：计算机工程杂志2018年第6期北京时间：
作者：陈硒,刘志雄
单位：1.中南大学湘雅二医院 信息网络中心,长沙 410011; 2.长沙学院 计算机工程与应用数学学院,长沙 410022
摘要：针对现有路径覆盖算法较少考虑传感器移动距离最小的现状,在证明最小传感器移动路径覆盖是NP难问题的基础上,提出一种启发式路径覆盖算法。通过路径离散化寻找冗余节点和冗余路径,从而逐步移动传感器,使其最终覆盖整条路径且移动总距离最小,并通过分析得出m个传感器覆盖路径中n个点的算法时间复杂度为O(n4m+n3m2)。仿真实验表明,在路径点数量和系统参数改变的情况下,该算法可有效降低时间复杂度,缩短移动距离。
关键词：无线传感器网络,目标追踪,路径覆盖,NP难问题,移动距离
基金资助：国家自然科学基金(61502057)。
