最小连通传感器覆盖及其相关问题

项目名称： 最小连通传感器覆盖及其相关问题

项目编号： No.61472272

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 伍伟丽

作者单位： 太原理工大学

项目金额： 84万元

中文摘要： 无线传感器已广泛应用于交通管制、环境监测、灾难预警、农田管理、战场指挥等经济活动及人类生活的各种领域。这些应用都离不开目标覆盖问题（Coverage Problem）。给出一组目标点或者一个目标区域，找出一组传感器使得它们的感知范围覆盖所有的目标点或者整个目标区域。这是关于无线传感器的一个基本问题。本项目是对最小连通传感器覆盖等 NP 难度优化问题的多项式时间近似算法的设计与分析。所选出的问题理论难度大，应用背景强。因此，研究结果对算法理论与无线传感器网络技术的发展均有重要意义。

中文关键词： 无线传感器网络；传感器覆盖；连通传感器覆盖；节能；近似算法

英文摘要： Wireless sensors have been widely used in controlling traffic, monitoring environment, warning disaster, managing farmland, commanding battlefield and other areas of economic activities and human life. These applications are inseparable from the target coverage problem. Given a set of target point or a target area to identify a set of sensors so that their perception of the scope to cover all of the target points or the entire target areas. This is a fundamental question about the wireless sensors.We propose to study approximation algorithms for several important NP-hard optimization problems on coverage in wireless sensor networks, for instance minimum connected sensor coverage problem, etc..The issues we have elected are difficult in theory and promising in application background. Therefore, solving them would have impact on the development of both algorithm theory and wireless sensor network technology.

英文关键词： wireless sensor networks;sensor cover;connected sensor cover;efficiency;approximation algorithm