Efficient Line K-Coverage Algorithms in Mobile Sensor Network

Abstract

In this paper, we address a new type of coverage problem in mobile sensor network, named Line K-Coverage. It guarantees that any line cutting across a region of interest will be detected by at least K sensors. We aim to schedule an efficient sensor movement to satisfy the line K-coverage while minimize the total sensor movements for energy efficiency, which is named as LK-MinMovs problem. We propose a pioneering layer-based algorithm LLK-MinMovs to solve it in polynomial time. Compared with a MinSum algorithm from previous literature to solve line 1-coverage problem, LLK-MinMovs fixes a critical flaw after finding a counter example for MinSum. We further construct two time-efficient heuristics named LK-KM and LK-KM+ based on the famous Hungarian algorithm. By sacrificing optimality a little bit, these two algorithms runs extremely faster than algorithm LLK-MinMovs. We validate the efficiency of our designs in numerical experiments and compare them under different experiment settings.

This work was supported in part by the State Key Development Program for Basic Research of China (973 project 2012CB316201), in part by China NSF grant 61422208, 61202024, 61472252, 61272443 and 61133006, CCF-Intel Young Faculty Researcher Program and CCF-Tencent Open Fund, the Shanghai NSF grant 12ZR1445000, Shanghai Chenguang Grant 12CG09, Shanghai Pujiang Grant 13PJ1403900, and in part by Jiangsu Future Network Research Project No. BY2013095-1-10. The opinions, findings, conclusions, and recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies or the government.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Wireless Sensor Network (WSN) nowadays attracts special attentions from scientific and technological community. Coverage is a fundamental problem among all challenges of WSN. Broadly speaking, coverage is a measure that determines how well a sensor network monitors objectives. Many variations of coverage problem have been proposed for different applications. As an example, the area K-coverage problem requires that each point in the area be covered by at least K sensors.

Barrier coverage is more applicable to monitor borders due to exploiting less sensors than area coverage. In front of or surrounding an area, a barrier is a belt-like region in which the sensors are spread. The barrier is said to be K-covered [2, 3] if every path that passes through the barrier touches the sensing range of at least K sensors. Many researchers considered line track rather than arbitrary pathes for barrier coverage [4–7], since in reality intruders usually go through a region with a line track. Moreover, intruders do not know any knowledge on distribution of sensors, they cannot figure out a “smart” path to follow. In [16], the authors proposed a MinSum algorithm to build a barrier by scheduling mobile sensors, so that any line intrusion will be detected by at least one sensor. We refer this problem as Line 1-Coverage problem.

In this paper, we consider an advance version of line 1-coverage problem: Line K-Coverage. A line is said to be K-covered if it is detected by at least K sensors. A region is called line K-covered if any line intrusion is K-covered. Usually, sensors at their initial positions may not form a line K-cover for the target region. Thus mobile sensors could move according to some strategy to form a line K-cover. For energy efficiency purpose, we hope that sensors will move with a shortest distance. In all, our optimization object is to minimize the sum of sensor movements to achieve the line K-cover for target region. We refer it as LK-MinMovs problem.

If the initial sensors deployment does not form a line K-cover, the target region will have “gaps” (K-uncovered intervals) against the intrusion. Due to the structural complexity, it is not easy to form line K-cover in one shot. A natural idea is to build line K-cover layer by layer because gaps have different degrees. We first fill up 1-level gaps by twofold overlaps, and then fill up 2-level gaps by threefold overlaps, until K-level gaps are filled. With this idea we propose a layer-based algorithm named LLK-MinMovs. For one layer repairing, a MinSum was proposed in a previous literature [16]. However, although authors in [16] claimed that MinSum outputs the optimal solution, it is not always correct. We illustrate the critical flaw of MinSum by a counter example, and fix the problem in our LLK-MinMovs algorithm. We also construct another two time-efficient heuristics named LK-KM and LK-KM+ based on the famous Hungarian algorithm. By sacrificing optimality a little bit, these two algorithms runs extremely fast with suboptimal results. We analyze the time complexity of them, and then validate their efficiency in numerical experiments under different experiment settings. To the best of our knowledge, we firstly solve the line K-coverage problem in mobile sensor networks, which has both theoretical and practical significance.

The rest of the paper is organized as follows. Section 2 introduces some related works. Section 3 presents the problem statement. Section 4 describes our layer-based algorithm (LLK-MinMovs) and gives its time complexity analysis. A counter example for MinSum is also introduced and corrected. In Sect. 5, we design LK-KM and its enhanced version LK-KM+. Numerical experiments are presented in Sect. 6. Finally, Sect. 7 gives conclusion.

2 Related Works

In the research area of mobile sensor networks, several recent literatures considered the strategy of mobile sensor movement to cover a region of interest, for example [9, 10]. Unlike the problem considered in this paper, they aimed to form an area coverage rather than barrier coverage for the region of interest.

Some of the existing works focus on line coverage [8] in a region. Baumgartner et al. [5] proposed the track coverage problem. Their objective is to place a set of sensors in the region such that the chance of detecting the path tracks by at least some given number of sensors is maximized. Other path coverage metrics are defined in [6, 7] by analytical expressions for any random deployment in a region. Balister et al. [4] defined a coverage metric called trap coverage which measures the longest distance an intruder can achieve within the region before touching the sensing range of any sensor.

In terms of mobile sensor for barrier, distributed algorithms are proposed in [11] to schedule mobile sensors for forming a barrier. Bar-Noy et al. [12] studied the problem of maximizing the coverage lifetime of a barrier composed by mobile sensors with limited battery powers. How to guide sensor moving to improve the quality of barrier coverage are studied in [13]. All of them consider barrier coverage for path, this is not the objective of this paper. We focus on line K-coverage.

Czyzowicz’s work [16] is most related to our objective. The authors proposed MinSum algorithm for line 1-coverage problem which inspired us to design the LLK-MinMovs algorithm. However, MinSum cannot always output an optimal solution. We provide a counter example and correct it in our design, so that LLK-MinMovs could work optimally for arbitrary instance. We also provide numerical experiments to compare LLK-MinMovs with MinSum when $K=1$.

3 Problem Statement

Assume our region of interest is a rectangle with horizontal length of L (otherwise we can use the minimum bounding rectangle of this region). n sensors $s_{1},s_{2},...,s_{n}$ are randomly deployed in this region. Each sensor $s_{i}$ has coordinator $(x_{i},y_{i})$, regarding to left-bottom point (0, 0), with same sensing range R. Sensors can move freely in this region, but they are supported by nonrenewable battery powers.

Figure 1 is an example scenario (Assume $K=3$), where the intrusion direction is vertical against the rectangle. Hence, we could project $s_i$ horizontally as a line segment represented by interval $[x_{i}-R, x_{i}+R]$. Then, we just need to consider our problem on line segment [0, L]. To better describe our problem, we label sensors with their x-coordinate, and assume each sensor has distinct $x_i$ value in increasing order. Note that we should have “enough” sensors to satisfy a line K-coverage. Thus, initially we have $2Rn \ge KL$ to get a feasible solution.

Fig. 1.

An example of line coverage transformation (K=3).

Easy to see, if we want to form a line K-coverage, every point along the x axis in [0, L] should belong to as least K intervals transformed from sensors. However, as shown in Fig. 1, there are many intervals on x axis that are covered by less than K sensors, i.e. the interval $[x_4+R,L]$. We consider such intervals as gaps. Thus, to form a line K-cover is equivalent as to fill up the gaps along x axis after sensor projection. Note that gaps may have different degrees. Some gaps are already covered by several sensors (but less than K), while some other gaps are even bare. To describe a gap rigorously, we have the following definition.

Definition 1

(Line k -Covered Gap). A line k-covered gap, denoted as $gap_{i}^k$, is an interval which starts from the ending point of sensor $x_i$ and ends up to the starting point of sensor $x_{i+k}$, say, the interval $[x_i+R, x_{i+k}-R]$.

Easy to see, $gap_{i}^k$ is covered by $k-1$ sensors, and $x_{i+k} - x_i > 2R$ (otherwise they will overlap to each other). Three example gaps are shown in Fig. 1, which are line 1-covered $gap_{0}^1$, line 2-covered $gap_{5}^2$ and line 3-covered $gap_{4}^3$. We add two virtual sensors adhesively to the starting point and ending point of the target region. In this example, $s_0$ locates at $x_0=-R$, and $s_7$ locates at $x_7=L+R$. To illustrate our design, we have another definition for overlap intervals as follow.

Definition 2

(Line k -Covered Overlap). A line k-covered overlap, denoted as $overlap_{i}^k$, is an interval which starts from the starting point of sensor $x_{i+k}$ and ends up to the ending point of sensor $x_{i}$, say, the interval $[x_{i+k}-R, x_i+R]$.

Similarly, $overlap_{i}^k$ is covered by $k+1$ sensors, and $x_{i+k} - x_i < 2R$ (otherwise we cannot find an overlap interval). Thus, some sensors could move to cover other gaps. An example line 3-covered $overlap_{3}^3$ is shown in Fig. 1, which is covered by sensors $x_3$, $x_4$, $x_5$, and $x_6$ respectively.

We will move some sensors to fill up all gaps in [0, L]. Define the final position of sensor $s_{i}$ as $x^{f}_{i}$. Then the moving distance $d_{i}$ of $s_{i}$ is $|x^{f}_{i}-x_{i}|$. The LK-MinMovs problem is to find the final position for n sensors $s_{1},s_{2},\cdots ,s_{n}$, so that these sensors will form a line K-cover while the total sensor movements $\sum \limits _{i=1}^{n} \vert x^f_i-x_i \vert$ is minimized. We require sensor movement schedule obeying an order preservation restriction given by a Lemma in [16] and sensors cannot move out of [0, L].

In the following sections, we will introduce three algorithms to solve the LK-MinMovs problem.

4 A Layer-Based Algorithm for LK-MinMovs Problem

In our design, we plan to fill up the gaps in an ascending order of their coverage degree. Correspondingly, we fill up line 1-covered gaps first, then line 2-covered gaps, and so forth until filling the line K-covered gaps. During the procedure of filling the line k-covered gaps, we can use the line k-covered overlaps. This strategy is proved to be efficient and better than MinSum by experiments in Sect. 6.

4.1 LLK-MinMovs Algorithm

In our layer-based algorithm, named as LLK-MinMovs algorithm, we try to find the two closest overlaps and select a cheaper one to fill a target gap. Note that such movement process should maintain current coverage level. That means the algorithm will not bring new gaps or downgrade the current coverage quality.

Algorithm 1 is the pseudo-code of LLK-MinMovs. The inputs are an array $X[1\dots n]$ representing the initial positions of n sensors, the length of the region, L, the coverage degree, K, and the sensor radius, R. It returns an array $X^f[1\dots n]$ of n elements representing the final positions of sensors.

In Algorithm 1, Line 1 sets two virtual stable sensors to bound the region. Line 2 depicts the layer-based procedure. At each level $k \in [1, K]$, Algorithm 1 finds every line k-covered gap and fills them in a left-right order. The function isCovered(i, k) in Line 4 is a binary function to determine whether the interval $[x_i+R,x_{i+k}-R]$ is line k-covered at current stage. If there exists a $gap_i^k$, we find its left and right closest overlaps as potential candidates (Line 5-6), compare the cost to use them filling the gap according to cost functions $Lcost(\cdot )$ and $Rcost(\cdot )$, pick up the cheaper one, and move corresponding sensors to fill up $gap_i^k$ according a distance constraint function $Ldist(\cdot )$ and $Rdist(\cdot )$ to keep the current coverage level (Line 7-9). The “while” loop from Line 4 to 9 guarantees that we will fill up all k-covered gaps generated by each $x_i$.

Now, let us define the cost functions and distance constraint functions respectively. At the beginning of every iteration, we say one sensor has negative shift if it has moved to left and has positive shift if it has moved to right or stays still compared to its initial position. Define $shift_i$ as the shift distance of $x_i$.

Definition 3

(Left/Right Overlap Cost). For $gap^{k}_{i}$, the $l^{th}$ to $(l+k)^{th}$ sensors left to $x_i$ form $overlap_l^k$ and the $r^{th}$ to $(r+k)^{th}$ sensors right to $x_{i+k}$ form $overlap_r^k$. Let $NS^k_l$ ($PS^k_l$) be the set of sensors which have negative (positive) shift among $x_{l+k},x_{l+2k},\cdots ,x_{l+mk},\cdots ,x_i$ sensors, where $l+mk \le i$. Let $S^k_r$ be the set of $x_r,x_{r-k},x_{r-2k},\cdots ,x_{r-mk},\cdots ,x_{i+k}$ sensors, where $r-mk \ge i+k$. Then Eq. (1) computes the left/right overlap costs.

$$\begin{aligned} Lcost(l,i,k)= \vert PS^k_l \vert - \vert NS^k_l \vert , \qquad Rcost(i, r, k)= \vert S^k_r \vert . \end{aligned}$$

(1)

Definition 4

(Left/Right Overlap Shift Distance). Easy to know, the size of $gap^{k}_{i}$ is $x_{i+k}-x_i-2R$, the size of $overlap^{k}_l$ and $overlap_r^k$ are $x_l - x_{l+k} + 2R$ and $x_r - x_{r+k} + 2R$ respectively. Let $MinShift=\min \{\vert shift_i \vert \mid x_i \in NS_l^k\}$, which is the effect shift window. Then the left/right shift distance are

$$\begin{aligned} \left\{ \begin{array}{l} Ldist(l,i,k)= \min \{x_{i+k}-x_i-2R, x_l - x_{l+k} + 2R, MinShift\},\\ Rdist(i,r,k)= \min \{x_{i+k}-x_i-2R, x_r - x_{r+k} + 2R\} \end{array} \right. \end{aligned}$$

(2)

4.2 A Counter Example for MinSum Algorithm

Note that the shifting cost for the left and right overlaps are different. The left shifts for the right overlap only involve sensors whose shift values are zero or negative, while the right shifts for the left overlap involve sensors will all possible shift values. It is due to the left-to-right processing of the gaps. That means right shift will benefit those sensors which have moved left. The authors in [16] also considered the compensation by using similar cost functions for $K=1$. However, they did not consider the influence of right shift distance to the calculation of $Lcost(\cdot )$. We find that only if the movement strategy considers the shift window effect of the left overlap, the algorithm could work optimally. A counter example is shown in Fig. 2.

Fig. 2.

A counter example to algorithm in [16] (K=1).

In Fig. 2 (a) we give the original positions of 11 sensors. Figure 2 (b) shows the situation when the first 3 gaps are filled, and there is still a $gap^1_{7}$ with size g which is greater than unit distance a lot. The results are same for our algorithm and MinSum. We can see the left shifts of $x_4$ and $x_6$ are very small (Assume $x_6$ left shift 1 unit distance, $x_4$ left shift 2 units distance). Now the cost function Lcost(1, 7, 1) of $overlap^1_{1}$ equals to $4-2=2$ because 4 positive shifts ($PS^1_1=\{x_2,x_3,x_5,x_7\}$) and 2 negative shifts ($PS^1_1=\{x_4,x_6\}$). The cost function Rcost(7, 10, 1) of $overlap^1_{10}$ equals to 3 ($S^k_{10}=\{x_8,x_9,x_{10}\}$). So $overlap^1_{1}$ is the cheaper one. Figure 2 (c) shows the result using MinSum which exploits $overlap^1_{1}$ to fill $gap^1_{7}$. Figure 2 (d) shows our algorithm uses the effect moving window. Then Lcost(1, 7, 1) of $overlap^1_{1}$ is evaluated again since the negative shift of $x_6$ changes to positive, thus $Lcost(1,7,1)=5-1=4$. So $overlap^1_{10}$ is the cheaper one. Figure 2 (e) shows the result after using $overlap^1_{10}$ in our algorithm. MinSum fills $gap^1_{7}$ with additional $6\cdot g-2 \cdot (2+1)\cdot unit=6\cdot g-5\cdot unit$ movements while LLK-MinMovs just uses additional $3\cdot g$ movements. Obviously, Our algorithm is better when $g > > unit$. This is because MinSum does not consider the effect shift window which influences the cost calculation.

4.3 Time Complexity of LLK-MinMovs

For the LLK-MinMovs algorithm, there are K loops to cover each level gaps. For each loop, we consider the total times of movements. There are two types of movements, left-movement and right-movement. In each left-movement, either a gap or a overlap will disappear, thus the total times of left-movements $T_l \le T_{ol}+T_{gl}$, where $T_{ol}$ is the times of movement where an overlap disappears and $T_{gl}$ is the times of movement where an gap disappears. In each right-movement, a gap or a overlap will disappear or a sensor is moved back to its initial location. Similarly, we have $T_r \le T_{or}+T_{gr}+T_b$ where $T_b$ is the times of movement where a sensor is moved back. Since in our algorithm, neither a new gap or a new overlap will occur, we have $T_{gl}+T_{gr} = |gaps|$, $T_{ol}+T_{or} \le |overlaps|$ and $|gaps|+|overlaps|<n$. On the other hand, since any sensor will not move to the left after moving to the right, $T_b \le n$. Thus we get the total times of movement $T = T_l +T_r <2n$. For each movement, we will at most move n sensors, thus the time complexity is $O(Kn^2)$.

5 The Design of LK-KM and LK-KM+ Algorithms

We new design another two algorithms for LK-MinMovs problem based on the famious Hungarian Algorithm. They have better time efficiency in spite of sacrificing the optimality a little bit. But their results are still sub-optimal.

The basic idea is to place the sensors to several fixed points evenly distributed on the line segment [0, L]. Obviously, it is a perfect Line K-coverage to put K sensors at each virtual fixed points with 2R distance between two neighbors. Then we construct a complete bipartite graph (S, P, E). S represents the sensor set and P represents the virtual fixed point set. Each virtual fixed point has K copies for K-coverage. The edge weight w(s, p) is $L-distance(s,p)$, then the maximum matching for P is the solution of original LK-MinMovs problem. We can use the Kuhn-Munkres algorithm (also known as the famous Hungarian algorithm) [14, 15] to compute this matching. This algorithm is referred as LK-KM algorithm shown in Algorithm 2.

Besides, we enhance the LK-KM algorithm with an idea to pull back the sensors which do not need to go so far away from their original positions because the sensor redundance provides the chance. The line K-coverage enhanced KM algorithm, denoted as LK-KM+ uses $PullToLeft(\cdot )$ and $PullToRight(\cdot )$ are added using a function $move(\cdot )$ for movement back of each sensor. We give an example for function call on $move(\cdot )$ in PullToLeft, thus is $move(iK+j,iK+j,min(X[iK+j]-X^f[iK+j],X^f[iK+j+1]-X^f[iK+j],X^f[iK+j]-X^f[iK+j-K])$. It move $x_{iK+j}$ to left in a distance which is shortest one among its shift distance, distance between it and its later neighbor, and distance between it and its K-hops previous neighbor (they should form line K-cover together). The similar procedure in PullToRight.

For LK-KM algorithm, the complexity is $O((KL/2R)^2n)$. And for LK-KM+ algorithm, in spite of adding $move(\cdot )$ steps using only O(n) time, the total complexity of LK-KM+ is also $O((KL/2R)^2n)$, which is still better than LLK-MinMovs.

6 Numerical Experiments

In experiments, we mainly compare our LLK-MinMovs with MinSum, LK-KM, and LK-KM+. They are all implemented in C++. For each case, we ran each algorithm 100 times at random inputs and calculate the average sum of movement. We define the redundance rate as $\frac{LK}{2Rn}$. First of all, we verify that LLK-MinMovs have the best performance for line 1-coverage, which proves that the MinSum is not optimal. Let $L=1000, R=5$ and the results are shown in Fig. 3 (a). LLK-MinMovs is the best and MinSum is better than LK-KM+.

Next, we study the coverage level K. Here we set $K=1\; \text{ to }\; 10, L/R=20$ and redundance rate be 0.8. We can see LLK-MinMovs and LK-KM+ get more superiority than LK-KM when coverage level K is increasing. Figure 3(b) gives the results. In term of running time, Fig. 3(c) shows LK-KM+ outperforms LLK-MinMovs much more when coverage level K is increasing.

Fig. 3.

Comparison On LLK-MinMovs, MinSum and LK-KM+(LK-KM)

Then, we study influence on the result with different sensor redundance rate. Besides, we conduct 3 groups of experiments on different $L/R = 10,20\;and\;40$. And we set $L=1000, K=3$. Figure 4 shows that in all cases LLK-MinMovs has best performance. Three algorithms have the same result at redundance rate 1. Sensors need move less distance when L / R becomes bigger. The LK-KM+ also improves LK-KM very much and is very close to LLK-MinMovs.

Fig. 4.

Experiments on redundance rate and L / R ($L=1000, K=3$).

7 Conclusion

In this paper, we address the Line K-coverage problem (LK-MinMovs) in mobile sensor network. We first propose a polynomial time optimal layer-based algorithm LLK-MinMovs. It fixes a critical flaw for the MinSum algorithm designed in [16] for line 1-Coverage problem. We also designed two sub-optimal but faster algorithms, LK-KM and LK-KM+, based on Hungarian algorithm, which have good time complexity $O(\frac{K^2L^2n}{R^2})$ in comparison with LLK-MinMovs of $O(Kn^2)$ considering n is significantly bigger than K usually.