Approximation Algorithms For Multiple Coverage In Mobile Sensor Networks

Wireless Sensor Networks(WSN)is a multidisciplinary research field that was initially driven by military applications.However,with the advancement of technology and the reduction in production costs of sensor nodes,various applications have emerged,including habitat monitoring and intrusion detection.WSN enables the collection of various information from the physical world and improves people’s environmental awareness.To address the limitation of static sensor nodes and improve network coverage,mobile nodes have been introduced into WSN,which can approach static sensor nodes and help transmit sensing data,thereby reducing energy consumption.However,it remains a challenge to reduce distribution costs of sensors and collect more information.In other words,the problem raises how to reduce the number of used sensors and reduce the energy consumption of sensors.This article mainly focuses on the multi-coverage problem of unit disks(UDMC problem),which is known as a problem with broad applications in wireless sensor network monitoring.In this problem,the goal is to determine the locations where disks should be placed on the plane to cover all targets with the minimum number of disks.This problem is challenging and does not admit any polynomial time exact solution unless = .Therefore,we present approximation algorithms in both offline and online setting:(1)an offline 5-approximation algorithm with linear time and space complexity,which can be easily adapted as an online 5-competitive algorithm.(2)an improved offline algorithm that attains ratio 4 and an efficient online algorithm with a constant average update time and a competitive ratio of 6.Numerical experiments are conducted to empirically test and compare our proposed approximation algorithms.Finally,we devise the first PTAS by combining the shifting strategy with the scaling method.In conclusion,this article presents novel approaches including a PTAS to address the multi-coverage problem of unit disks in wireless sensor network monitoring.Our proposed approximation algorithms have been shown to be effective through extensive numerical experiments.