# A Distributed Approach to the Evasion Problem
## 1 Introduction  
As we enter the era of Internet of Things (IoT), sensors are becoming ubiquitous for many real world applications. Keeping the points of interest (PoI) or regions covered as much as possible by sensors is essential for sensor networks to accomplish information gathering, exploration, or monitoring. This often translates into two closely related problems that have been extensively studied in many different perspectives--the _coverage_ and the _evasion_ problems in static and mobile sensor networks, which have also attracted significant attention within the Topological Data Analysis community. The _Coverage_ problem aims to achieve the maximum coverage and robustness with optimal deployment in sensor networks, with respect to different metrics or tradeoff. The _Evasion_ problem [1; 2; 3] is the question of whether--given a collection of sensors and a particular movement pattern over time--it is possible to stay undetected within the domain over the same stretch of time. Each sensor has a limited sensing range and can only collect information within it. In certain settings, a PoI or a region needs to be covered at all times to ensure completeness of the data collection. Given the limited battery life of a sensor, one PoI may need to be covered by multiple sensors to ensure robustness of detection. On the other hand, solving the evasion problem is particularly useful for applications such as mineral exploration and disaster recovery, in which maximum coverage is not required at all times, especially when moving sensors deployment is possible. The Coverage problem in sensor networks has been studied extensively [4; 5]. Depending on the circumstances, the goal of covering a region can be modeled in various ways. Generally speaking, a coverage problem aims to achieve either area coverage or target coverage. In the area coverage problem, a continuous region of interest needs to be monitored for collecting information; while the target coverage problem usually deals with a set of points of interest(PoI) being monitored by the sensors. In general, the level of coverage can be different depending on the underlying applications. For example, for tracking a target, simple coverage [6] requires that every point in the region is covered by at least one sensor. K-coverage [7; 8] improves the reliability from simple coverage by considering the fact that sensors may run out of battery or be out of service for various reasons, thus each target point needs to be covered by at least \(k\) sensors. Q-coverage [9] evolves from k-coverage, in which a coverage vector \(Q\) is introduced to define desired level of coverage for each target point. When full coverage is not required, there are many partial coverage models that emphasize for different scenarios, in which the coverage could be only up to a certain level \(p\). There are also models focusing on specific points of interest or certain path in the target region. For example, barrier-coverage [10] is one particular model that covers the boundary of a region and can be useful for intrusion detection, and monitoring animals etc. The target coverage problem may also be considered to be partial coverage problem of an entire region. Sweep coverage [11] is another partial coverage model where PoI is periodically monitored. The study of Topological Data Analysis on sensor coverage and evasion problems was initiated in [1; 12; 13], in which the authors identified a sufficient and necessary criterion for coverage based on relative homology. Their work inspired several follow-up attempts. In [14], the authors construct a distributed algorithm for homology computation and demonstrate it on a solution for distributed computation of the homology-based coverage criterion. Simultaneously, [15] uses zig-zag persistent homology to localize coverage holes in both static and dynamic sensor networks. The first sufficient and necessary criterion for the evasion problem was introduced in [2]. Our paper is built on this work [2] but with significant extensions.