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

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.

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

覆盖问题是在无线传感网络研究中的重要课题。在自2015年1月1日至2018年12月31日期间，在本项基金的支持下，我们对于传感器覆盖问题按照申请书的计划做了系统的研究，同时我们对社交网络的若干热点展开了初步研究探讨。在传感器覆盖上，我们研究了边界覆盖的质量以及安全性，有向传感器网络中弱栅栏覆盖构建，全视角强栅栏覆盖，基于迭代加权虚拟力算法的DSNs覆盖，等等。在社交网络上，我们研究了关于影响力最大化的Bharathi-Kempe-Salek猜想，谎言传播的阻断问题，社区划分等核心问题。在这些研究中，我们获得了许多成果。利用这些成果完成了总计41篇论文，其中34篇刊出在杂志，7篇发表在会议文集。特别是，有12篇发表在SCI/SCIE类杂志里，有4篇论文发表在CCF A类的杂志和会议文集里。