摘要： 针对现有路径覆盖算法较少考虑传感器移动距离最小的现状,在证明最小传感器移动路径覆盖是NP难问题的基础上,提出一种启发式路径覆盖算法。通过路径离散化寻找冗余节点和冗余路径,从而逐步移动传感器,使其最终覆盖整条路径且移动总距离最小,并通过分析得出m个传感器覆盖路径中n个点的算法时间复杂度为O(n4m+n3m2)。仿真实验表明,在路径点数量和系统参数改变的情况下,该算法可有效降低时间复杂度,缩短移动距离。

关键词: 无线传感器网络, 目标追踪, 路径覆盖, NP难问题, 移动距离

Abstract: Most of existing algorithms for path coverage do not consider minimization of sensors movement distance.Aiming at this situation,this paper proves that the above mentioned problem is NP-hard,and presents a heuristic path covering algorithm.It moves sensors through techniques of path curve discretization,redundant sensors and redundant paths,resulting in coverage of the whole path with minimum movement distance of sensors.It gets analysis results that,when m sensors cover n points on the path,the time complexity of the algorithm is O(n4m+n3m2).Simulation experiments illustrate that the proposed algorithm can reduce time complexity and moving distance when the number of path points and system parameters change.

Key words: Wireless Sensor Network(WSN), target tracking, path coverage, NP-hard problem, movement distance

中图分类号: 

• TP393