A novel multi-objective coverage optimization memetic algorithm for directional sensor networks

Abstract

For the target problem of a directional wireless sensor network, the greedy algorithm can easily fall into the local optimal solution, whereas the genetic algorithm must forecast the lifetime of the upper bound of the network. We propose a novel multi-objective coverage optimization memetic algorithm that encodes the solutions as chromosomes and simulates the biological evolution process in search for a favourable solution to address the aforementioned problems. Experimental results show that the proposed algorithm can prolong the network lifetime more effectively than similar heuristic algorithms in other studies.

Keywords

Directional sensors target problem memetic algorithm network lifetime

Introduction

In recent years, wireless sensor networks (WSNs) have been the focus of increasing attention and have been extensively used in environmental monitoring, traffic control, patient monitoring and intrusion detection.^1,2 Given their calculation, monitoring, communication and other functions,³ many wireless sensors are organized into WSNs autonomously through communication to complete the task of monitoring specific areas. Wireless sensors have several advantages, including their small size and low power consumption. However, these sensors have limited battery power and cannot be easily changed after deployment.⁴ Therefore, the energy efficiency of WSNs must be investigated. Methods for energy perception routing, data transmission control, energy-efficient data transmission and aggregation, data compression and sensor node scheduling have been proposed to improve the energy efficiency of WSNs from different aspects.⁵

Based on different coverage goals and requirements, WSNs can be divided into target coverage, area coverage and barrier coverage.⁶ Deng et al.⁷ proposed that the regional coverage problem can be converted into the target coverage problem. Cardei et al.⁸ and Zorbas et al.⁹ argued that the target coverage can cover a set of targets under the condition that wireless sensors and targets are randomly and uniformly deployed in the area and that wireless sensors can monitor all targets. For the target coverage problem, wireless sensors must continuously monitor all targets. The continuous monitoring of all targets is crucial in extending the network lifetime. Wireless sensors have four states, namely, transmission, reception, idle and sleep.⁸ Although energy consumption in the transmission, reception and idle states is greater than that in the sleep state, this problem can be simplified because wireless sensors can only switch between the active and sleep states.¹⁰ Therefore, scheduling wireless sensors is a simple and effective method for extending the network lifetime.¹¹

The omnidirectional wireless sensor has a circular monitoring area. Singh and Lobiyal,¹² Liu et al.¹³ and others proposed different methods based on the scheduling protocol to extend the network lifetime of WSNs that consist of omnidirectional wireless sensors. Directional wireless sensors only sense a sector of a disk at a specific time. Video sensors,¹⁴ ultrasonic sensors,¹⁵ infrared sensors¹⁶ and other directional sensors are used more extensively. In directional sensor networks (DSNs), the sensors can only sense one direction that does not overlap with the other directions. This restriction makes the target coverage problem in directional WSNs more complex than that in omnidirectional WSNs because directional WSNs need to determine the state and sensing direction of the sensor simultaneously. Similar to literature,¹⁷ we discuss the directional characteristic only from the sensing aspect, and similar to literature,¹⁸ we randomly and uniformly deploy directional sensors in the target area. The consumed energy during communication between wireless sensors is ignored, whereas the sensors are connected with one another through mobile robots or a large communication range¹⁹ to solve the target coverage problem of the DSN.

The cover set comprises sensors that can monitor all targets, with each sensor working in only one sensing direction. Gil and Han¹⁸ proposed a maximum cover set for addressing the Maximum Set Covers for DSNs (MSCD) problem in DSNs, which involves the identification of cover sets that can monitor all targets in an energy-efficient way and the maximization of network lifetime by assigning different scheduling times to each cover set. The cover set in the DSN can be classified into disjoint and non-disjoint. In the disjoint cover set, each sensor can only appear in one cover set, whereas in the non-disjoint cover set, each sensor may appear in more than one cover set. This study proposes a multi-objective coverage optimization memetic algorithm (MOCOMA) to solve the target coverage problem of the DSN.

The remainder of this article is organized as follows: section ‘Related work’ introduces the related target coverage algorithms of the directional WSN. Section ‘Assumption and definition’ discusses the relevant assumptions and definitions in this article. Section ‘Proposed algorithm’ discusses the proposed algorithm. Section ‘Simulation and analysis’ examines the proposed algorithm through a simulation and then analyses and compares the results with those of the two other algorithms. Section ‘Conclusion’ summarizes the article.

Related work

Cardei and Du²⁰ defined the disjoint coverage problem as an NP-complete problem. Liu et al.¹³ proposed distributed algorithms for scheduling sensors that negotiate their respective states through communication. Zorbas et al.⁹ proposed two greedy heuristic algorithms that extend network lifetime by finding and monitoring the key targets first. Lai et al.²¹ used the genetic algorithm (GA) for solving the NP-complete problem that encodes the candidate solutions as chromosomes, simulates the Darwinian evolution mechanism and facilitates the crossover, mutation and elimination of the coding chromosome to obtain the final solution. Cardei et al.⁸ defined the maximum cover set problem as that where each sensor can be involved in multiple cover sets and then applied the linear programming and greedy methods to solve such problem. The aforementioned methods can effectively solve the target coverage problem of a WSN that comprises omnidirectional wireless sensors, but these algorithms are unsuitable for the target coverage problem in directional WSN.

Many scholars^22,23 assumed that the number of sensing directions of each sensor is provided and that the directions are randomly distributed in [0, 2π] when solving the target coverage problem of the directional network. Ai and Abouzeid²⁴ assumed that the directions of a sensor does not overlap with the other directions; therefore, a target can only belong to one direction of a sensor. Ai and Abouzeid ²⁴ used only a few directions to cover more targets under the limitation that one sensor cannot appear in the same cover set in several instances. This article extended the network lifetime by producing more cover sets. Gil and Han ¹⁸ proposed two heuristic algorithms that are based on the greedy and GAs to address the target coverage problem of the DSN. Although the greedy algorithm can rapidly solve the problem, the results are significantly influenced by the search method and, in several cases, may fall into the local optimal solution. By contrast, the algorithm based on the GA needs to forecast the upper bound of the network lifetime. However, Ting and Liao ²⁵ reported that this upper bound cannot be easily estimated. Cai et al.²³ proved that the target coverage problem is an NP-complete problem and then proposed a greedy algorithm to derive a disjoint cover set. Cai et al.²³ proposed a linear-programming-based algorithm to solve such problem. However, this method has high complexity and requires a long runtime to solve the problems.

This study has the following contributions to the target coverage problem of the DSN: (1) propose a new MOCOMA, (2) design a new chromosome structure that is suitable for the proposed algorithm, (3) enhance the operations to convert the solutions toward the favourable direction faster, (4) propose a suitable algorithm for deriving the disjoint and non-disjoint cover sets and (5) examine such algorithm through experiments and comparisons.

Assumption and definition

This study assumes that monitoring area A is a two-dimensional plane area, in which length is L and width is W. M targets and N directional sensors are uniformly and randomly deployed in area A. A sink node or base station which has unlimited energy can obtain targets and sensors’ positions and control the modes of the sensor nodes. All directional sensors are homogeneous but have limited and irreplaceable battery power. Each sensor has several sensing directions. The sensing region is a sector of the sensing disk, and the sensing regions of different directions of a sensor are not overlapping. The directional sensors in area A must monitor all targets continually. Similar to literature,¹⁸ this study only discusses the directional sensors from the sensing function aspect and does not consider the communication aspect. Sensors can be in either active or sleep states. The awake sensors are responsible for monitoring the targets, whereas the remaining sensors stay in the sleep state to save battery. The energy consumptions of the switching states and adjusting directions are negligible. The relevant variables are defined in Table 1.¹⁷

Table 1.

Variables and definitions.

Variables	Definitions
M	the number of targets
N	the number of directional sensors
W	the number of sensing directions per sensor
Esi	the energy of sensor si
t_m	the mth target, m∈ {1, 2, …, M}
s_i	the ith directional sensors, i∈ {1, 2, …, N}
d_i,j	the jth sensing direction of sensor si
D_i,j	the targets that are covered by d_i,j
T	the set of targets, T = {tj\|1 ≤ j ≤ M}
S	the set of sensors, S = {si\|1 ≤ i ≤ N}

We propose an algorithm to solve the MSCD problem in the literature.¹⁸ The network in Figure 1 comprises three targets and three directional sensors. t_m (1 ≤ m ≤ 3) represents the target and s_i (1 ≤ i ≤ 3) represents the directional sensor, with each having three sensing directions. The targets can be monitored by the active d_i,j , with {d _1,3, d _2,2, d _3,1} and {d _1,3, d _2,1, d _3,3} represent two possible cover sets that can accomplish the monitoring task. A reasonable use of sensors can prolong the network lifetime.

Figure 1.

Example of three directional sensors and three targets.

Proposed algorithm

We propose the MOCOMA to solve the MSCD problem. Under a limited energy and direction, this algorithm tries to find more cover sets to prolong the network lifetime. The solutions to the problem are encoded as chromosomes, and the biological evolution process is simulated in the algorithm. The selection, enhancement and elimination processes are performed to improve the solutions until the algorithm obtains the optimal solution. We initially introduce the proposed algorithm integrally and then each part of the algorithm is introduced in detail. This algorithm can search for a better solution in the global solution space more easily than the greedy algorithm.

Algorithm structure

The memetic algorithm draws from Lamarckism that the offspring can inherit the knowledge and features of its parents. Compared with the GA, the memetic algorithm does not need to forecast the network lifetime, and the enhancement operation is added to the algorithm to promote the search for a global optimal solution. The proposed algorithm can also avoid the local optimal solution more effectively than the greedy algorithm. Table 2 shows the pseudocode of the proposed algorithm. The algorithm is divided into chromosome representation, fitness function and enhancement parts. The candidate solutions are encoded as chromosomes (line 6) that can be expressed by different data structures according to the characteristics of the problem. The N chromosomes are initialized randomly as the initial population P. The fitness function is used to evaluate the candidate solutions (line 7). For a specific problem, the higher the fitness value of the chromosome, the better. The local enhancement operation transforms the selected chromosome (lines 15–16). Then, the algorithm tries to find a better solution. After obtaining a new chromosome, the worst solution in MP is eliminated. The algorithm repeats the selection, enhancement and elimination processes until the maximum number of iterations is reached (lines 11–20). After reaching the maximum number of iterations, the algorithm takes the best solution in MP as the final solution and calculates the runtime of the selected sensors (lines 21–23). The energy of the sensors will be updated according to the solution, and those sensors without energy will be removed from S (line 24). The algorithm performs from lines 5–25 repeatedly until all targets cannot be monitored by the remaining sensors simultaneously.

Table 2.

Pseudocode of MOCOMA.

Algorithm: Multi-objective coverage optimization memetic algorithm
01. Input: Directional network Net = (S, T), number of sensing directions W, working time t_k
02. Require: S≠∅, T≠∅, W>0
03. Runtime = 0
04. C = ∅
05. while each target is covered by at least one direction of sensors do
06. initial population P
07. Evaluate P
08. repeat
09. Select the pareto-optimal individual in P and add it into Mating Pool MP
10. until the number of individuals in MP reaches pts
11. while until termination do
12. P_s = Select( MP )
13. P_t = ∅
14. ~empty( P_s ){
P_t = Optimizer( P_s )
15. P_t = Improver( P_s )
16. }
17. Evaluate P_t
18. MP = Survival( MP, P_t )
19. end
20. P_max = MaxFitness( MP )
21. C = C ∪ P_max
22. Runtime = Runtime +CalculateRuntime( P_max )
23. Update sensor’s lifetime in S
24. end
25. return( C, Runtime )

MOCOMA: multi-objective coverage optimization memetic algorithm.

Chromosome structure

The candidate solutions are encoded as chromosomes, and each chromosome is mapped to a point in the solution space. The chromosome is a one-dimensional array, as shown in Figure 2.

Figure 2.

Structure of chromosome.

N represents the number of sensors in S, 2N represents the length of the one-dimensional array and the odd and even positions of the array represent the sensor ID and sensing direction, respectively. The numbers of positions 1 and 2 in Figure 2 are denoted as 3 and 1, respectively, which that sensor 3 works with sensing direction 1. All numbers on the odd position are different from one another. When creating the population, the values of a chromosome are randomly initialized under the premise of satisfying equation (1):

{\begin{matrix} chromosome (2 i - 1) \in {1, 2, \dots N} \begin{matrix} i \in {1, 2, \dots N} \end{matrix} \\ ⋃_{p = 1}^{N} chromosome (2 p - 1) = {1, 2, \dots N} \\ chromosome (2 j) \in {1, 2, \dots W} \begin{matrix} j \in {1, 2, \dots N} \end{matrix} \\ chromosome (2 i - 1) \neq chromosome (2 j - 1) \begin{matrix} i, j \in {1, 2, \dots N} \land i \neq j \end{matrix} \end{matrix},

(1)

Each chromosome is a candidate solution of the problem. The number of cover sets contained in a chromosome is calculated from position 1 to N of the chromosome and combined with the targets that the sensors used currently cover. On position i, if all targets in set T are covered, then the sensors currently comprise a cover set. Then, the sensors that are used in the next cover set are recalculated from position i + 2. This process is repeated until i > N. The chromosome in Figure 3 contains k cover sets, and the sensors of each cover set can cover all targets.

Figure 3.

Example of cover sets.

Fitness function

As an evaluation standard of chromosomes, the fitness function is crucial for obtaining a solution. For the chromosome structure in Figure 2, the fitness function evaluates a chromosome from the following aspects: number of cover sets in the chromosome, variance in the remaining energy of sensors in a cover set and number of unused sensors. Equation (2) shows the fitness function that is used in this study:

{\begin{matrix} F (chromosome (i)) = τ * CoverNum + ε * E Variance + φ * UnusedSensor \\ τ + | ε | + φ = 1, \begin{matrix}  \end{matrix} (0 \leq τ, φ \leq 1) \land (- 1 \leq ε \leq 0) \end{matrix},

(2)

(1) Number of cover sets (CoverNum)

When calculating the number of cover sets in a chromosome, we find an eligible cover set from left to right. Figure 3 shows k cover sets, with each cover set monitoring all targets. If each cover set runs a round, then the total runtime of a chromosome is computed as follows:

T_{r} (chromosome (i)) = \sum_{a = 1}^{k} t_{a},

(3)

In equation (3), k denotes the number of cover sets that are contained in the chromosome and t_a is the runtime of the ath cover set. The sensors that do not belong to any cover set remain in the sleep state, and the chromosome with a larger T_r value can be easily selected.

(2) Variance in the remaining energy of sensors in a cover set (EVariance)

The variance reflects the fluctuation in the data. A cover set with a small variance indicates that the remaining energy of sensors in the cover set are close, which is beneficial in extending the network lifetime. Equation (4) is used to calculate the variance of a chromosome:

V_{chromosome (i)} = \frac{1}{K} (\sum_{a = 1}^{K} \sum_{b = 1}^{n_{a}} (\frac{1}{n_{a}} {(l_{a, b} - \frac{1}{n_{a}} (\sum_{b = 1}^{n_{a}} l_{a, b}))}^{2})),

(4)

In equation (4), k represents the number of cover sets in a chromosome, the ath cover set contains n_a sensors and l_a,b indicates the remaining energy of the bth sensor in the ath cover set.

(3) Number of unused sensors (UnusedSensor)

When calculating the cover set that a chromosome contains from left to right, if all sensors after the ith position cannot monitor all of the targets, then these sensors are called unused sensors:

UnusedSensor = \frac{n_{l}}{N},

(5)

In equation (5), n_l denotes the number of unused sensors, whereas N denotes the total number of sensors. When the number of cover sets is similar, a larger number of unused sensors indicates that more sensors can participate in the construction of cover sets in the future, which is beneficial in extending the network lifetime.

The algorithm use the fitness function to evaluate chromosomes. Through many rounds of screening, chromosomes with high fitness values will survive and the algorithm eliminates the chromosomes with low fitness values. Keeping chromosomes with high fitness values is easier to acquire better solutions, thus the algorithm can obtain a longer network lifetime. The chromosome is evaluated from three aspects: number of cover sets and total runtime in the chromosome, variance in the remaining energy of sensors in a cover set and ratio of unused sensors. A higher fitness value means that the total runtime of cover sets in a chromosome is longer, variance in the remaining energy of sensors in a cover set is smaller and ratio of unused sensors is higher. A chromosome with longer total runtime achieves a longer network lifetime. Making the variance in a cover set smaller is beneficial to balance the energy consumption of network, it can prolong the network lifetime. If two chromosomes are similar in these two aspects, the chromosome that has higher ratio of unused sensors can make more sensors obtain the opportunities to participate in constructing cover sets in the future, it can achieve the goal of prolonging the network lifetime. Thus, for achieving a longer network lifetime, the fitness function should be used for screening chromosomes.

Figure 4 is an example of the fitness function, chromosome A and B are both consisted of s ₁∼s ₆, the remaining energy of s ₁∼s ₆ are 1, 1, 2, 3, 4, 6. According to the remaining energy of sensors, the runtime of cover set a and b in chromosome A are 1 and 2, and the runtime of cover sets in chromosome B are 1 and 3. S ₆ does not participate in any cover set, therefore, it is a sleep sensor. In this example, CoverNum is major, the other two aspects are auxiliary. The values of τ, ε and φ are set as 0.5, −0.25 and 0.25, therefore, F(A) = 0.89 and F(B) = 1.45, F(B) > F(A). The algorithm will keep chromosome B and eliminate chromosome A, if DSNs schedule the sensors according to the chromosome B, DSNs can use fewer sensors to achieve a longer network lifetime, it is beneficial to prolong the network lifetime.

Figure 4.

Example of fitness function.

Enhancement operation

The algorithm transforms the selected chromosome through an enhancement operation to obtain a new solution. Combined with the selection and elimination operations, the solution is transformed toward the favourable direction. The enhancement operation can be divided into two parts, namely, optimizer and improver. The algorithm switches between these two phases to select reasonable sensors for constructing new cover sets. When the remaining sensors in the chromosome are unable to construct a new cover set, the enhancement operation is completed. Then, the new chromosome P_t is initialized according to the order that sensors are selected when constructing the cover sets. Those sensors that do not belong to any cover set are arranged at the end of chromosome P_t .

Optimizer: When constructing a new cover set, the optimizer phase is responsible for selecting and adding the initial sensor to the new cover set. The critical target refers to the target that is monitored by the fewest number of sensing directions. Given that all targets must be monitored simultaneously, the critical targets serve as the bottleneck of the entire network. The algorithm selects a sensing direction that can monitor the critical target randomly and add the selected sensor to the new cover set. Afterward, the algorithm switches to the improver phase.

Improver: The new cover set is constructed completely in the improver phase. The algorithm adds reasonable sensors to the cover set continuously according to the condition in which the targets have been covered and the sensors have been used. This operation is repeated until all targets are covered. A new cover is constructed afterward. This procedure is presented in detail as follows:

Step 1: Assuming that sensor s_a is added to the new cover set in the optimizer phase, the set of uncovered targets is computed as T _cur= T − D_a,w , where D_a,w denotes the targets that are covered by the wth sensing direction of sensor s_a .

Step 2: If all sensors have been used, then the enhancement operation is completed. Otherwise, we use equation (6) to evaluate the unselected sensors. If sensor s_c obtains the highest fitness value when working in the qth sensing direction, then sensor s_c will be added to the cover set.

Step 3: Update set T _cur. The targets that are monitored by the qth sensing direction of s_c will be removed from T _cur.

Step 4: If T _cur is empty, then the new cover set is constructed completely and the algorithm enters the optimizer phase to construct the next cover set. Otherwise, the algorithm executes step 2.

{\begin{matrix} F_{s} (d_{i, j}) = η * (\frac{| T_{cur} \cap D_{i, j} |}{| T |}) + μ * (\frac{| (T - T_{cur}) \cap D_{i, j} |}{| T |}) \\ η + μ = 1 \land 0 \leq η, μ \leq 1 \end{matrix}

(6)

In equation (6), D_i,j is a target set that is covered by sensing direction d_i,j . The algorithm constantly enters the optimizer and improver phases. The enhancement operation is terminated when all conditions are satisfied. Then, a new chromosome, P_t , is constructed.

Selection and elimination

Table 2 shows two kinds of selection operations. The selection operation in line 9 is used to select m Pareto optimal chromosomes to construct a new candidate population MP. The chromosome P_s , which has the smallest fitness value, is selected by the other selection operation in line 12. The algorithm will transform P_s to obtain a new chromosome P_t in the following steps: P_s and P_t , which have larger fitness values, will be added to MP and another chromosome will be eliminated. The solutions in MP will be transformed toward a favourable direction through the selection, enhancement and elimination operations. Thus, the algorithm can obtain favourable solutions.

Simulation and analysis

We use MATLAB to examine the proposed algorithm. We assume that the area to be monitored, area A, is a 100 m × 100 m fixed area, 30 targets are randomly and uniformly deployed in this area, all directional sensors are homogeneous, and the network lifetime is counted by round. For each experiment, we generate 30 topologies and execute every algorithm on each topology. We take the average value of the experiments as the result of each algorithm. The proposed algorithm is compared with GA¹⁸ and GA¹⁷ from the aspects of network lifetime. The experimental results show that the proposed algorithm outperforms the GA¹⁸ and GA¹⁷ in terms of extending the network lifetime.

Effect of the number of sensors

We test the three algorithms for prolonging the network lifetime under different numbers of sensors. All sensors are assumed to have three sensing directions, with each sensor sensing only one of these directions. Each direction has a central angle of 2π/3(W = 3) and does not overlap with the other two directions. The sensing radiuses of all sensors are 20 m. Figure 5 shows the network lifetime that is obtained by the three algorithms when the number of sensors varies from 100 to 300.

Figure 5.

Influence of the number of sensors on network lifetime.

The network lifetime that is obtained by the three algorithms increases along with the number of sensors that are deployed in area A. MOCOMA outperforms GA¹⁸ and GA¹⁷ in extending the network lifetime. Figure 6 shows the average number of sensors per cover set that is used by the algorithms under different numbers of sensors.

Figure 6.

Number of sensors per cover set.

MOCOMA uses a lesser number of sensors per cover set than the other two algorithms, which indicates that MOCOMA has a better choice strategy. Given that a lesser number of targets are covered by each sensor overlap in a cover set, the number of sensors that are used in each cover set is also lessened. MOCOMA selects the solutions many times, which is beneficial in finding better solutions and more reasonable sensors for constructing a cover set.

Effect of sensing range

In the simulation, we test the performance of the algorithms in extending the network lifetime according to the changes in the sensing ranges of the directional sensors. The number of sensors in area A is assumed to be 150, with each sensor only sensing one of the three directions with an angle of 2π/3(W = 3) and does not overlap with the other two directions. We examine and compare the performance of the three algorithms when the sensing ranges of the sensors vary from 20 m to 40 m.

Figure 7 shows the network lifetime that is obtained by each algorithm under different sensing ranges. MOCOMA obtains a longer network lifetime than the other two algorithms. Moreover, when the sensing range is 36 m, MOCOMA achieves the greatest enhancement as compared with the other algorithms.

Figure 7.

Influence of sensing range on network lifetime.

Effect of the number of sensing directions

We fix the number of sensors to 150 and the sensing range of each sensor to 20 m to investigate the influence of the number of sensing directions. Then, we examine the performance of all algorithms in prolonging network lifetime according to the changes in the number of sensing directions.

As shown in Figure 8, MOCOMA outperforms the other two algorithms in prolonging the network lifetime. In each test case, all algorithms achieve the longest network lifetime under four directions, which indicates that, under a fewer number of directions, the sensors in a cover set can easily overlap the sensing area, thereby wasting the energy of the sensors and shortening the network lifetime. By contrast, under a large number of sensing directions, more sensors are needed to construct a cover set, thereby shortening the network lifetime.

Figure 8.

Influence of the number of directions on network lifetime.

Conclusion

This study discusses the target coverage problem in directional WSNs. Compared with traditional WSNs, directional WSNs must consider the states and working sensing directions of the sensors, thereby making these networks a highly complex, NP-complete problem. We propose the MOCOMA to solve the target coverage problem in directional WSNs. The algorithm encodes the solutions as chromosomes and simulates the biological evolution process through the selection, enhancement and elimination processes. The solutions are changed toward favourable directions. Then, favourable solutions are obtained after several rounds. We evaluate the performance of the proposed algorithm according to the following experimental factors: number of sensors, sensing range and number of sensing directions of each sensor. According to the experimental results, the MOCOMA achieves a longer network lifetime than the other two algorithms.

Footnotes

Academic Editor: Suat Ozdemir

Declaration of Conflicting Interest

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

This research was supported by National Nature Science Foundation of China (grant nos 61073164 and 61373123); The Fund of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education (93K172012K05) and Key Development Program for Science and Technology of Jilin Province, China (grant nos 20120301 and 20150414004GH).

References

Carrabs

Cerulli

D’Ambrosio

. Maximizing lifetime in wireless sensor networks with multiple sensor families. Comput Oper Res 2015; 54: 121–137.

Raffaele

Monica

Andrea

. Maximizing lifetime and handling reliability in wireless sensor networks. Networks 2014; 64: 321–338.

Degirmenci

Kharoufeh

J P

Prokopyev

O A

. Maximizing the lifetime of query-based wireless sensor networks. Acm Trans Sen Netw 2014; 10(4): 1–24.

Zhou

Krishnamurthy

. Models and solutions for radio irregularity in wireless sensor networks. ACM Trans Sens Netw 2006; 2(2): 221–262.

Mostafaei

Meybodi

. Maximizing lifetime of target coverage in wireless sensor networks using learning automata. Wireless Pers Commun 2013; 71(2): 1461–1477.

Ahmadi

Shojafar

Hajeforosh

. An Efficient Routing Algorithm to preserve k-coverage in wireless sensor networks. J Supercomput 2013; 68(2): 599–623.

Deng

. Transforming area coverage to target coverage to maintain coverage and connectivity for wireless sensor networks. Int J Distrib Sens Netw 2012; 11(5): 1497–1500.

Cardei

Thai

. Energy-efficient target coverage in wireless sensor networks. IEEE INFOCOM, 2005; 3:1976–1984.

Zorbas

Glynos

Kotzanikolaou

. Solving coverage problems in wireless sensor networks using cover sets. Ad Hoc Net 2010; 8(4): 400–415.

10.

Cerulli

Donato

Raiconi

. Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges. Eur J Oper Res 2012; 220(1): 58–66.

11.

Tian Georganas

. A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of Acm International Workshop on Wireless Sensor Networks & Applications, Atlanta, USA, 2002, pp. 32–41.

12.

Singh

Lobiyal

. Energy preserving sleep scheduling for cluster-based wireless sensor networks[C]// Contemporary Computing (IC3). In: 2013 Sixth International Conference on IEEE, Noida, 8–10 August 2013, pp. 97–101.

13.

Liu

Suo

Sun

. A virtual square grid-based coverage algorithm of redundant node for wireless sensor network. J Netw Comput Appl Noida, 8–10 August 2013; 36(2): 811–817.

14.

Feng

Code

Kaiser

. Panoptes : scalable low-power video sensor networking technologies. Acm T Multim Comput 2005; 1(2): 151–167.

15.

Djugash

Singh

Kantor

. Range-only slam for robots operating cooperatively with sensor networks. In IEEE Int’l Conf. on Robotics and Automation (ICRA, 2006:2006), pp. 2078–2084.

16.

Manolov

Guilera

Sierra

. An analysis of a large scale habitat monitoring application. In: International Conference on Embedded Networked Sensor Systems, SENSYS, Baltimore, Md, November 2004, pp. 214–226.

17.

Mohamadi

Salleh

Ismail

. Scheduling algorithms for extending directional sensor network lifetime. Wirel Netw 2015; 21(2): 611–623.

18.

Gil

Han

. A target coverage scheduling scheme based on genetic algorithms in directional sensor networks. Sensors 2011; 11(2): 1888–1906.

19.

Tekdas

Isler

Lim

. Using mobile robots to harvest data from sensor fields. IEEE Wirel Commun 2009; 16: 22–28.

20.

Cardei

. Improving wireless sensor network lifetime through power aware organization. Wirel Netw 2005; 11(3): 333–340.

21.

Lai

Ting

. An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), Singapore, 25–28 September 2007, pp. 3531–3538. IEEE.

22.

Cai

Lou

. Target-oriented scheduling in directional sensor networks. In: Proceedings of the IEEE INFOCOM, 2007, Vol. 58, pp. 1550–1558.

23.

Cai

Lou

. Energy efficient target-oriented scheduling in directional sensor networks. IEEE Trans Comput 2009; 58(9): 1259–1274.

24.

Abouzeid

. Coverage by randomly deployed wireless sensor networks. J Comb Optim 2006; 52(6): 2658–2669.

25.

Ting

Liao

. A memetic algorithm for extending wireless sensor network lifetime. Inf Sci 2010; 180(24): 4818–4833.