一种传感器移动距离最小的路径覆盖算法.doc

(录用定稿) 网络首发时间: 2017-12-01 16:06:29
GB/T 7714-2015 格式参考文献:陈硒;[J/OL]. 计算机工程, :1-3. (2017-12-01). .hebeu./kcms/detail/.. .
一种传感器移动距离最小的路径覆盖算法
陈硒刘志雄
中南大学湘雅二医院信息网络中心长沙学院计算机工程与应用数学学院
导出/参考文献已关注关注
X
关注成功!
加关注后您将方便地在我的关注中得到本文献的被引频次变化的通知!
分享
新浪微博
腾讯微博
人人网
开心网
豆瓣网
网易微博
收藏打印
摘    要:
目标追踪是传感器网络的重要应用之一。用户更关注目标移动路径的覆盖而非整个监测区域的覆盖。已有路径覆盖算法并未考虑传感器移动距离最小的情况。该文首先证明最小传感器移动路径覆盖问题是NP-难的, 然后提出一种启发式路径覆盖算法。通过路径离散化, 寻找冗余节点和冗余路径来逐步移动传感器, 使得最终覆盖整条路径, 且传感器移动总距离最小。分析表明, m个传感器覆盖路径中n个点的算法时间复杂性为O (n4m+n3m2) 。仿真实验评估了系统参数R1和R2以及路径点数量对传感器移动距离的影响。
关键词:
无线传感器网络; 目标追踪; 路径覆盖; NP难; 最小移动;
作者简介:陈硒(1982-) , 女, 工程师, 硕士, 主要研究方向为无线传感器网络(@) ;
作者简介:刘志雄(1982-) , 男, 讲师, 博士, 主要研究方向为无线传感器网络(lzxterry@)
基金:国家自然科学基金资助项目()
A path coverage algorithm with minimum movement of sensors
Chen Xi Liu Zhixiong
work Center, Xiangya Hospital of Central South University; School puter Engineering and Applied Mathematics, Changsha University;
Abstract:
Target tracking is one of the core applications in works. In this kind of applications, the user is often concern about the coverage of targets' moving paths, rather than in the whole area. Existing algorithms for path coverage do not consider the situation of minimum movement of sensors. Firstly, this paper proved that the problem is NP-hard, and then presented a heuristic path covering algorithm. It moved sensors through techniques of path curve discretization, redundant sensors and redundant paths, resulting in coverage of the path with minimum movement of sensors. Analysis shows, when m sensors cover n points on the path, the plexity of the algorithm is O (n4m+n3m2) . Simulations are conducted to evaluate the effects of some parameters, such as R1, R2, and the number of path points, on the moving distance of sensors.
Keyword:
wireless works; target tracking; path coverage; NP hard; minimum movement;
1 引言
无线传感器网络(wireless works, WSNs) 的目的是协作感知、获取和处理目标对象的信息, 然后发送给用户[1]。在入侵监测和目标跟踪等场景下, 用户主要关注入