当前位置: 首页  科学研究  学术交流  学术报告

数学交叉科学研究所学术报告(郭龙坤教授 齐鲁工业大学)

发布者:戴 情   发布时间:2021-12-01  浏览次数:141

数学交叉科学研究所学术报告

报告人:郭龙坤(齐鲁工业大学计算机科学与技术学院教授)

报告题目:Barrier and Target Coverage with Mobile Sensors on the Plane

报告时间:2021年12月4日(星期六)9:30-10:30

腾讯会议号:625-419-088

报告摘要:Emerging IoT applications have brought up new coverage problems with mobile sensors. In this talk, we shall introduce several results on linear barrier coverage and on-a-line target coverage with mobile sensors distributed on the plane. We first address the computational complexity and algorithmic results for min-max line barrier coverage (LBC) problem that aims to minimize the maximum movement of the sensors for the sake of balancing energy consumption. Then we focus on the MinSum Sink-based Line Barrier Coverage (SLBC) problem of covering a line barrier with mobile sensors originated at sink stations on the plane, where the objective is to minimize the movement sum of the sensors for the sake of energy efficiency. When the sinks emit sensors with non-uniform radii, we prove the MinSum SLBC problem is NP-complete via reducing from the Partition problem. Then for the MinSum Sink-based on-a-Line Target Coverage (SLTC) problem of covering targets on a line, an exact algorithm is presented based on grouping the targets and transforming to the shortest path problem in the auxiliary graph induced by the vertices corresponding to the groups. The algorithm runs in quadratical time when sinks emit sensors of uniform sensing radius, and can be extended for the case of sensors of non-uniform radii. Experiments were carried out to demonstrate the practical performance gain of our algorithms.

报告人简介:2005与2011年分别毕业于中国科学技术大学计算机科学与技术系获工学学士与博士学位。2015年-2016年到阿德莱德大学计算机学院做博士后(Research Associate)研究工作。2017年担任国家自然科学基金委员会数学天元基金全国“组合优化”研究生暑期学校班主任。主要研究兴趣为计算机网络、并行与分布式计算、数据科学、算法设计与组合优化。至今共发表国内外主流学术期刊与会议论文六十余篇,包括IEEE Transactions on Mobile Computing(TMC), IEEE Transactions on Computers(TC), IEEE Transactions on Parallel and Distributed Systems (TPDS),Algorithmica等顶级国际期刊及ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)、International Joint Conference on Artificial I


邀请人:张昭