报告题目：移动传感器网络的节能栅栏覆盖问题研究

报告人：李双娟 博士

报告时间：2019年7月14日上午10:00—12:00

报告地点：数计学院4号楼229会议室

报告摘要：

  Intrusion detection is an important application of wireless sensor networks (WSNs). Given a set of mobile sensors and their initial positions, how to move these sensors to a region border to achieve barrier coverage energy-efficiently is challenging. This paper studies the 2-D MinMax barrier coverage problem of moving n sensors in a two-dimensional plane to form a barrier coverage of a specified line segment in the plane while minimizing the maximum sensor movement for the sake of balancing battery power consumption. Previously, this problem was shown to be NP-hard for the general case when the sensing ranges are arbitrary. It was an open problem whether the problem is polynomial-time solvable for the case when sensors have a fixed number of sensing ranges. We first study the barrier coverage problem for the general case and propose a two-phase algorithm and a greedy algorithm. The approximation factor of the two-phase algorithm is proved to be √2 for the case when the sensors can exactly cover the barrier. We then study a special case of great practical significance that the sensors have the same sensing range and present an O(n²log n) time algorithm. We obtain Θ(n³) candidate values for the minimum maximum sensor movement by deriving a necessary condition of the optimal sensor deployment and find the optimal sensor movement among them by using an efficient search procedure and a decision algorithm. To the best of our knowledge, this is the first result for solving the 2-D MinMax barrier coverage problem both for the general case and the uniform case.

报告人简介

李双娟博士工作于华南农业大学数学与信息学院。2005年获得武汉大学信息安全学士学位，2007年获得武汉大学计算机科学与理论硕士学位，2007年-2013年曾在中国电子科技集团公司第七研究所工作，2016年获得中山大学计算机科学与技术博士学位。主要从事无线自组织网络、无线传感器网络的协议、算法设计。曾在网络领域顶级会议INFOCOM、权威期刊Computer Network等发表论文。目前主持一项国家自然科学基金青年项目。主要参与的项目曾获得中国电子科技集团公司一等奖。