Keywords

1 Introduction

Wireless sensor networks(WSNs) are multi-hop and self-organized networks which consist of one or multiple sink nodes and many sensor nodes. A sensor node can collect sensing data, process and transmit the data to its neighbors. The sink node is responsible to receive data from sensor nodes and inform users the environment of networks. Barrier coverage in wireless sensor networks is widely used in border surveillance. It is inspired by the moats which are used to detect and prevent intruders trespassing [4]. Compared with area coverage or target coverage, barrier coverage has the advantage of requiring fewer sensor nodes. Sensor nodes whose sensing ranges overlap and cover the length of monitoring region form a 1-barrier coverage as shown in Fig. 1.

Fig. 1.
figure 1

An example of 1-barrier coverage.

Full size image

Many literatures have studied the network lifetime and energy efficiency for area coverage and target coverage such as [6, 12–15]. Like area coverage and target coverage, the network lifetime and energy efficiency are also important issues for barrier coverage. Gage et al. [1] firstly propose the concept of barrier coverage. The are two kinds of barrier coverage which are strong barrier coverage and weak barrier coverage. Kumar et al. [4] define the notion of k-barrier coverage using wireless sensor nodes and propose efficient algorithms to determine whether a region is barrier covered. They also prove the critical condition of weak barrier coverage. Liu et al. [7] prove the critical condition of strong barrier coverage. They devise an efficient distributed algorithm to construct strong barrier coverage with low communication overhead and low computation cost. Kumar et al. [8] propose optimal network lifetime strong barrier coverage algorithms. They prove an important theorem which is the optimal network lifetime of k-barrier coverage is m/k where m is the maximum number of node-disjoint paths. Ban et al. [11] define weak barrier coverage and propose a distributed algorithm for constructing weak barrier coverage. Chen et al. [9] introduce the concept of local barrier coverage and devise an efficient algorithm to construct local barrier coverage with a limitation that the crossing path of an intruder is bounded in a small rectangle box. Yang and Li [10] study the minimum energy cost k-barrier coverage problem by assuming each sensor has l+1 sensing power levels and propose two heuristic algorithms. The above works only consider sensing in barrier coverage. They simply treat that each sensor node can communicate with the sink node directly. However, the communication range is not large enough if a sensor node is far from the sink node. Thus we consider not only sensing but also communication in barrier coverage under multi-hop wireless sensor networks. According to [3], the communication consumes about 75 % energy of a sensor node. The communication energy efficiency is also an important factor for minimum energy cost barrier coverage problem. Du [5] states that data aggregation can reduce overall traffic given the limited bandwidth of a sensor node which saves energy. In this paper, we adopt data aggregation instead of data gathering in transmitting data to the sink node. As communication consumption is much higher than the computation cost [2], the energy cost of communication is mainly concerned with the number of hops from a sensor node to the sink node. The bigger the number of hops, the larger transmission latency. In the intruder detection, the sink node need to collect the data from sensor nodes periodically such that a transmission latency constraint is required.

Yang and Li [10] solve minimum energy cost k-barrier coverage problem by minimizing total sensing energy of sensor nodes. Based on the results of them, we extend this problem by considering another important factor communication energy cost and solve the problem in a different aspect: given the location of the sink node and sensor nodes with discrete levels of transmission power and a transmission latency constraint. Our goal is to minimize the individual node’s maximum energy cost for barrier coverage subject to the transmission latency constraint by adjusting the power levels. Minimizing the individual node’s maximum energy cost is significant because minimizing total energy cost does not guarantee minimizing the individual node’s energy cost. If the individual node’s sensing range is large, it is soon exhausted. Otherwise the individual node can last for longer time if its sensing range is small which means that there are more sensor nodes to be substituted. The contributions of our research are summarized as follows:

  1. 1.

    We propose an efficient distributed algorithm to minimize the sensing energy cost 1-local barrier coverage. Then based on Divide and Conquer method, we construct none-crossing k-barrier coverage.

  2. 2.

    Given k-barrier coverage and a transmission latency bound \(t_b\), we construct a data aggregation tree T that satisfies nodes in barriers transmitting data to the sink node within latency \(t_b\).

Above all we minimize the individual node’s maximum energy cost for barrier coverage subject to the latency constraint. We call it the MIME problem. The rest of the paper is organized as follows: Sect. 2 presents the network model, Sect. 3 proposes algorithms for minimum sensing energy cost 1-local barrier coverage and none crossing k-barrier coverage, Sect. 4 solves the problem of minimum communication energy cost for barrier coverage. Section 5 presents our simulation results, Sect. 6 concludes this paper.

2 Network Model

We assume there are n sensor nodes randomly deployed in a monitoring region B. Each sensor node’s sensing model and communication model are disk models. The radius of the sensing is denoted as \(R_s\) and the radius of the communication is denoted as \(R_c\). Both of them have discrete power levels. The power levels vary from 0 to k where k is the maximum power level. \(R_c\) is assumed to be larger than \(R_s\) at the beginning. When the sensing power level increases, the communication power level increases correspondingly which means we always maintain \(R_c>R_s\). Some definitions are shown as below:

Definition 1

(Coverage Graph G(V,E) [8]): The coverage graph is generated by the sensor network. V contains all sensor nodes and two virtual nodes while E contains all edges. There exists an edge between two sensor nodes in V whose sensing range overlaps. Two virtual nodes s and t are placed to the left of the monitoring region and to the right of the monitoring region respectively. There exists an edge between s(t) and a sensor node u if u’s sensing range covers the left(right) border of the monitoring region.

Definition 2

(Crossing Barriers): Two barriers \(B_1\) and \(B_2\) are said to be crossing barriers if and only if there is at least a pair of edges crossing in their coverage graph. Figure 2 is an example of crossing barriers.

Fig. 2.
figure 2

An example of crossing barriers.

Full size image

Definition 3

(MIME Problem): The MIME problem is minimizing the individual node’s maximum energy cost problem. Given a wireless sensor network N over a monitoring region B, each sensor node u has k+1 adjustable sensing power levels and k+1 adjustable transmission power levels. With a certain latency constraint \(t_b\), our goal is to minimize the individual node’s maximum energy cost for barrier coverage subject to \(t_b\). The individual node’s maximum energy cost contains the sensing energy cost and the transmission energy cost.

3 Minimum Sensing Energy Cost

In this section, we focus on minimizing individual node’s maximum sensing energy cost for barrier coverage. Firstly, we propose an efficient distributed algorithm to construct 1-local barrier coverage which guarantees sensor nodes in the barriers maintain the minimum sensing power levels. Then we construct none-crossing k-barrier coverage by the method of Divide and Conquer. Finally, we analyze the performance of our algorithms.

A. Minimum sensing energy cost 1-local barrier coverage

Minimum sensing energy cost 1-local barrier coverage is an efficient distributed algorithm. Each sensor node is assigned with the minimum sensing power level at the beginning. They increase their sensing power level progressively and maintain a boolean variable Flag which is used to direct themselves to adjust the sensing power level. Flag is set to be true initially. In Step 1, a sensor node u whose boolean variable is true attempts to increase one sensing power level and examines whether there is a new neighbor. If u’s sensing range covers the left(right) border of the monitoring region, the virtual node s(t) is considered as u’s new neighbor. If u’s sensing range covers a new sensor node v, then it adds v to its neighbor list and sends a Request Message to v. If u covers none of the new sensor nodes, it maintains the current sensing power level and waits for next round. When the number of u’s neighbors is equal or bigger than 2, its boolean variable is set to be false which means in the next round, it does not change its sensing power level. Because sensor node u and its current neighbors have formed local strong barrier coverage. There is no need to increase its sensing power level to find more neighbors.

In Step 2, each sensor node u handles its received messages. There are three kinds of messages which are Request Message, Positive Message and Negative Message. The Request Message is used to inquiry a sensor node’s neighbor list. The Positive Message and the Negative Message are the response of Request Message. After receiving a Request Message, if the number of u’s neighbors is smaller than 2, u begins to adjust its communication power lever to communicate with the sender, then it adds the sender as its new neighbor and returns a Positive Message, otherwise it return a Negative Message to the sender. When u receives a Positive Message, it adds the sender to its neighbor list while when u receives a Negative Message, it keeps its neighbor list the same. After Step 2, each sensor node goes back to the Step 1 and continues the next round.

figure a

B. None-crossing k-barrier coverage

In Kumar [8]’s study, he adopts the standard max-flow algorithm to compute the maximum number of node-disjoint paths and schedule these node-disjoint paths to construct k-barrier coverage. One node-disjoint path forms 1-barrier coverage. However, the max-flow algorithm does not guarantee none-crossing k-barrier coverage. In the coverage graph as Fig. 2, \(B_1\) and \(B_2\) represent two barriers. According to Kumar [8]’s optimal scheduling algorithm, \(B_1\) works until it is exhausted, then \(B_2\) takes the place of \(B_1\). However, \(B_1\) and \(B_2\) are crossing barriers, if an intruder I is at the location as the Fig. 2 shown, then \(B_2\) can’t prevent I trespassing. Because after \(B_1\) is exhausted, I is under \(B_2\) which means sensor nodes in \(B_2\) can’t detect I any more. With this disadvantage, the network lifetime of barrier coverage decreases. Our goal is to construct none-crossing k-barrier coverage with the minimum energy cost.

In Algorithm 2 we adopt Divide and Conquer method to construct none-crossing k-barrier coverage. Initially, we call Algorithm 1 to compute a barrier B whose sensor nodes maintain the minimum sensing power level. When the density of node deployment is large enough, local barrier coverage can guarantee the global barrier coverage. Then we divide the redundant sensor nodes into two groups based on the constructed barrier B. For each group, we recursively call Algorithm 1 to compute the next barrier until the sensor nodes of current group can not form a barrier.

figure b

C. Performance evaluation

In each round of Algorithm 1, each sensor attempts to increase a sensing power level. When the number of a sensor node’s neighbors is bigger or equal to 2, it does not increase its sensing power level. Such that Algorithm 1 can converge very soon because as a sensor node’s sensing range increase, it can easily find two neighbors. The biggest communication overhead of the network happens when Algorithm 1 runs not long. At that time, the average number of neighbors of each sensor node is one. After that, the communication overhead becomes smaller and smaller. If the number of sensor nodes in the network is n, then the biggest communication overhead is O(n). But most of time the communication overhead is smaller than O(n).

In Algorithm 2, we adopt Divide and Conquer method to avoid constructing crossing barriers. In each branch, we call Algorithm 1 to compute whether there exists a barrier. With the depth of the branch tree growing, the number of sensor nodes in each subgroup decreases. The largest communication overhead of constructing none-crossing k-barrier coverage is O(nlogn). Such that our proposed algorithms for minimizing sensing energy cost barrier coverage have low communication overhead and they are efficient.

4 Minimum Communication Energy Cost

In this section, we aim to minimize the communication energy cost of the individual sensor node. In Sect. 2 we assume that the transmission power level increases corresponding with the sensing power level. After minimizing the sensing energy cost of the individual in Sect. 3, the individual sensor node maintains a low transmission power level. However, it can’t guarantee that the data can be transmitted to the sink node under the latency constraint \(t_b\). Because it needs more redundant sensor nodes as relay nodes to transmit data such that the transmission latency becomes larger. In the following study, we propose an algorithm to construct a data aggregation tree T subject to the latency constraint \(t_b\) by adjusting the individual sensor node’s transmission power level.

In Algorithm 3, we construct a complete graph CG from G firstly. The length of each edge e(u,v) is represented by the number of hops between u and v. Then we call Kruskal algorithm to produce an MST from CG. We can generate an aggregation tree T by substituting each edge in MST with the corresponding path in G. From Step 5 to Step 13, we modify T to satisfy the latency constraint \(t_b\). We traverse the sensor nodes of barriers which are the source nodes one by one. We use \(P_uc\) to denote a sensor node u’s transmission power level and \(P_k\) to denote the maximum transmission power level. If the latency \(t_u\) from a sensor node u to the sink node s beyond \(t_b\), then the shortest path from u to s in G is added to T. After that, if \(t_u\) still beyond \(t_b\), then u increases its transmission power level gradually to find a shorter path to s.

figure c

5 Simulations

In this section, we do extensive simulations by Java and Matlab to evaluate the performance of our algorithms. We present the average results from 100 separate runs of algorithms in the figures. Our simulations contains two parts:

In the first part, we compare the algorithms for the minimum sensing energy cost k-barrier coverage with two heuristic algorithms of Yang and Li [10]. The network parameters are set to the same as they do. Sensor nodes are randomly deployed in a 100\(\,\times \) 5 m rectangular monitoring region. Each sensor node has four different sensing ranges which are 0,4,6,8 and four sensing power levels which are 0,16,36,64. Yang and Li [10] study the effect of number of sensor nodes on the total sensing energy cost. Our algorithms aim to minimize the individual node’s maximum sensing energy cost which is a different aspect. We add up each sensor node’s sensing energy and do the comparing. In Figs. 3 and 4, “Heuristic-1” and “Heuristic-2” are two heuristic algorithms of Yang and Li [10]. “Distributed” is our proposed algorithm. We can see that “Distributed” has better performance than “Heuristic-1” and approaches to “Heuristic-2”. Our distributed algorithm not only maintains minimum individual node’s maximum sensing cost but also obtains low total energy cost.

Fig. 3.
figure 3

Total sensing energy cost versus the number of sensor nodes with k = 5

Full size image
Fig. 4.
figure 4

Total sensing energy cost versus the number of sensor nodes with k = 8

Full size image

In the second part, we evaluate our algorithm through transmission energy cost and transmission time. We set the transmission power model: \(P_c(u,v)\) = \(d^2\) (u,v). \(d^2\) (u,v) is the distance in terms of number of hops between two sensor nodes u and v. We use max\(\{\) d(u,s) \(|\) u \(\in \) barriers \(\}\) to denote the longest shortest path from senor nodes in barriers to the sink node s. The latency bound ratio \(B_r\) is equal to \(\alpha \Delta \max \{\) d(u,s) \(|\) u \(\in \) barriers \(\}\) where \(\alpha \) is latency bound which varies from 1.5 to 2.5 and \(\Delta \) is the maximal degree of T. Figure 5 shows the transmission energy cost versus the number of barriers, we can see that when \(\alpha \) is strict latency bound or loose latency bound, the transmission energy costs are similar. When \(\alpha \) is equal to 2.2 which is not strict and loose, the transmission energy cost is lower in general. Figure 6 shows the transmission time versus the number of barriers, we can see that after the number of barriers reaches to 6, the transmission time converges slowly because the transmission time is concerned with the depth of data aggregation tree T. When the number of source nodes reaches to a threshold that T sustain, more source nodes does not increase the transmission time. When the latency bound is strict, the transmission time is smaller. This is actually expected as strict latency bound makes the depth of the aggregation tree T smaller.

Fig. 5.
figure 5

Transmission energy cost versus the number of barriers

Full size image
Fig. 6.
figure 6

Transmission time versus the number of barriers

Full size image

6 Conclusion

In this paper, we study the problem of minimizing the individual node’s maximum energy cost for barrier coverage subject to the latency constraint. We consider not only the sensing energy cost but also the transmission energy cost. We develop an efficient distributed algorithm to construct 1-local barrier coverage with minimum sensing energy cost. We also propose an algorithm to construct none-crossing k-barrier coverage. Then based on the methods of minimum spanning tree and shortest path tree, we construct a data aggregation tree under latency constraint by adjusting transmission power levels. For the future work, we will study the interference between neighbor barriers and construct interference-free k barrier coverage.