Minimizing Total Sensor Movement for Barrier Coverage by Non-uniform Sensors on a Line

Abstract

Barrier coverage is a cost effective approach for intruder detection applications. It relies on monitoring the perimeter, or barrier, around the area of interest by placing sensors at appropriate locations on the barrier. In this paper we consider the problem of barrier coverage of a line segment by moving sensors along the line containing the segment. We extend the results existing in the literature by considering the case of non-uniform sensors placed at initial positions that do not overlap with the interval of interest.

R. Benkoczi and D. Gaur—These authors acknowledges the support for this research received from an NSERC Discovery Grant.

Z. Friggstad—This research was undertaken, in part, thanks to funding from the Canada Research Chairs program.

A Appendix

1.1 A.1 Proofs from Sect. 3

Proof

(of Lemma 1 ). Let S be a collection of sensors covering the barrier [0, L]. If the sensors of S are ordered from right to left and labeled accordingly by the indices $s_1$, $s_2, \ldots s_{|S|}$, then the cost of the barrier is

$$\begin{aligned} c(S) = |S| \cdot L - \sum _{i=1}^{|S|} (|S| - i) \cdot 2r_{s_i} + \sum _{i=1}^{|S|} d_{s_i} \end{aligned}$$

(4)

where L, $r_i$ and $d_i$ assume the definitions given above. If S is fixed, then c(S) is minimized by maximizing $\sum _{i=1}^{|S|} (|S| - i) \cdot 2r_{s_i}$. This is accomplished by re-ordering the index so that $r_{s_1} \ge r_{s_2} \ge \ldots \ge r_{s_{|S|}}$.

Proof

(of Lemma 2 ). We have $OPT \le Z$ because Z corresponds to the movement in a feasible solution. To see that $Z \le n \cdot OPT$, let $X = \max _{i \in S^*} |x_i|$ where $S^*$ is the set of sensors moved in an optimum solution. Let $OPT = OPT_1 + OPT_2$ where $OPT_1 = \sum _{i \in S^*} |x_i|$. Think of $OPT_1$ as the cost of moving the optimum intervals from their start positions to 0 and $OPT_2$ as the cost of moving them from 0 to their final positions.

Consider the iteration of the greedy algorithm that uses sensors i with $|x_i| \le X$. An upper bound on the cost of moving them from their start positions to 0 is $n \cdot X \le n \cdot OPT_1$ and an upper bound on moving them further to their final destinations is $OPT_2$. This is because greedily moving by length is optimum if all start positions are 0. Therefore, $Z \le n \cdot OPT_1 + OPT_2 \le n \cdot OPT$.

Proof

(of Lemma 3 ). We prove the first statement of Lemma 3 by induction on i, with the case $i = 0$ being trivial. So, suppose $i > 0$. If $f(i, k\zeta ) = f(i-1, k\zeta )$ then there is nothing to prove. Otherwise, let c be such that $f(i-1, k\zeta ) = f(i-1, (k-c)\zeta ) - 2r_i$ and $|f(i-1,(k-c)\zeta ) - r_i - x_i| \le c\zeta$. By induction, we can cover $[f(i-1, (k-c)\zeta ), L]$ using the first $i-1$ intervals with cost at most $(k-c) \cdot \zeta$. Extending this to a cover of $f(i,k\zeta )$ costs at most $c\zeta$, which proves this part of the claim.

The second statement is also proved by induction on i, with the case $i = 0$ again being clear. So, let $i > 0$ and let x be such that the first i sensors can cover [x, L] with total movement cost at most z. Say $S'$ is the collection of sensors used in this cover. If $S_i \not \in S'$, then by induction we have $f(i-1, (k+i-1)\zeta ) \le x$ so $f(i, (k+i-1)\zeta ) \le x$ as well. But $f(i, (k+i)\zeta ) \le f(i, (k+i-1)\zeta )$ also holds (by the recurrence) so $f(i, (k+1)\zeta ) \le x$ as required.

So, suppose $S_i \in S'$. Without loss of generality (by Lemma 1), we may assume that $S_i$ is the leftmost sensor in the cover of [x, L] and that $S_i$ moves $m_i := x+r_i-x_i$ to its position in this cover (this will be positive, otherwise we are saying sensor i was moved left, in which case it can be discarded from $S'$ to get an even cheaper solution). Let c be such that $c \zeta \le m_i < (c+1) \cdot \zeta$, so the remaining sensors in $S'-\{S_i\}$ have total movement at most $z-m_i \le (k-c)\zeta$ in this cover. Now, $S' - \{S_i\}$ covers $[x+2r_i, L]$ with cost at most $x-m_i$ so $f(i-1, (k-c+i-1)\zeta ) \le x+2r_i$ by induction. Because $|f(i-1, (k-c+i-1)\zeta ) - r_i - x_i| \le x+r_i - x_i = m_i < (c+1) \cdot \zeta$, then by the recurrence for g (when the $\min$ indexes with $c+1$) we have $f(i, (k+i)\zeta ) \le x$.

Proof

(of Lemma 4 ). If we assume a complete barrier coverage containing consecutive sensors $S_i$, $S_j$ such that $x_i < 0$, $x_j > L$, and $x_i + m_i > x_j + m_j$, then the paths the sensors travel can be “uncrossed”, so that $S_i$ takes the former place of $S_j$ and vice versa. Since the distance traveled by either sensor is only decreased by uncrossing, it follows that there exists some optimum barrier coverage without crossed sensors.

Proof

(of Lemma 5 ). We can eliminate overhang on one side of any complete barrier coverage as follows. Suppose we have a coverage with the uncrossed property, so that there exists a unique $x^*$ with $n_L$ sensors originally positioned to the left of the barrier covering $[0,x^*]$ and $n_R$ sensors originally positioned to the right covering $[x^*,L]$. Suppose without loss of generality that $n_L \ge n_R$ and that overhang is present on both sides of the barrier. Each sensor in the coverage can be shifted contiguously to the left until the rightmost point covered by the sensor overhanging [0, L] on the right is shifted to L. Since $n_L \ge n_R$, the reduction in cost required to move the left-side barriers to their new positions is no less than the added cost of moving the right-side barriers further to the left. Therefore, we obtain a coverage without right overhang at equal or lesser cost. A symmetric argument works in the case that $n_L \le n_R$.