Multiobjective Coverage Control Strategy for Energy-Efficient Wireless Sensor Networks

Abstract

A multiobjective optimization coverage control strategy is proposed for solving the contradictory problem among energy consumption, equilibrium of energy, and network coverage in wireless sensor networks. A new evolutionary algorithm named Multiobjective free search algorithm (MOFS) is designed for WSN optimization problem based on fitness functions and binary coding schemes. The proposed strategy is used to estimate the number of active nodes because individual nodes cannot have their working state information readily. Simulation shows that MOFS is effective to solve the typical combinatorial optimization problem, and the coverage control strategy can obtain high network coverage and reduce energy consumption effectively by the reasonable selecting parameters, while equilibrium of energy consumption is also considered.

1. Introduction

The current interest in wireless sensor network (WSN) stems from the potential of using sensing devices to explore environment of the planet. To accomplish this type of exploration, sensor nodes must have the ability to self-configure into a communication network and provide energy-efficient data transmission. Coverage control problem is one of the most fundamental issues in wireless sensor networks, because it is a measure of the quality of service (QoS) in a sensor network [1]. Sensor nodes in network are usually equipped with batteries with limited power. Therefore, energy conservation operations are critical for extending network lifetime [2].

Wireless sensor network has emerged as a promising tool for monitoring the physical world. It utilizes self-organizing networks of battery-powered wireless sensors that can sense, process, and communicate [3]. The optimal set of active nodes selection has been proved as an NP-complete problem with random WSN network topology [4]. Heuristic algorithm is an effective way to solve this problem. PEAS is a well-known protocol proposed by [5]. By the protocol, some nodes will become redundant nodes that need not be activated, as long as the other nodes exist within sense area of the inactivated nodes. The centralized and distributed greedy algorithms have been proposed based on randomized algorithm, so that nodes set can cover target area as large as possible [6]. The approach of [7] effectively extends network lifetime by alternating the active or sleep state of node. The linear programming method is used to obtain the minimum active nodes set to keep coverage [8]. And the coverage uniformity is considered simultaneously. pCover protocol is proposed by [9]. The protocol is only based on local information without the need of time synchronization. Voronoi diagram is used to calculate the worst path and the most effective path in sensor networks [10]. The aforementioned coverage control algorithms are trying to extend network lifetime under the condition that QoS is guaranteed. However, to the best of our knowledge, it is found that the least number of active nodes does not represent that network performance is the best in random network topology. The balance of network energy consumption is also the key factor to determine lifetime and operation stability of entire network.

Intelligent computing has been applied to wireless sensor network coverage control because of adaptability and optimization capabilities. The target area is divided into grid, and genetic algorithm is used to seek maximized coverage under certain total price [11]. Particle swarm optimization is specially used for subcluster sensor networks that are based on maximum entropy clustering in large-scale wireless sensor networks. Then mobile nodes are arranged to achieve complete coverage [12]. The study in [13] uses $(μ + λ)$ evolution strategy to find the smallest active node set to complete monitoring tasks. The methods mentioned above regard coverage as the optimized goal without considering network energy balance or using random network topology model. Authors in [14] optimize network coverage and nodes utilization simultaneously by using improved NSGA-II to obtain the control of WSN network coverage. A multiobjective hybrid method is proposed to solve dynamic coverage and connectivity problem (DCCP) for sensor node failure in flat WSN [15]. Genetic algorithm is used to improve the current DCCP solution.

In this paper, a new multi-objective optimization coverage control strategy for energy efficient wireless sensor network is presented, in which a new multi-objective free search (MOFS) algorithm based on the characteristics of WSN is also introduced. Network coverage and network energy equilibrium are the two goals optimized by MOFS in WSN coverage control. The main contributions of this paper are threefold. First, a framework for optimizing the tradeoff between network coverage and network equilibrium energy consumption is developed. The developed framework is an example of MOFS algorithm for combinatorial optimization problems. Next, the proposed strategy not only ensures the minimum nodes utilization, but it also takes the balance of entire network energy consumption into account. Finally, simulation results are presented to characterize the performance of our strategy. Results indicate that the new coverage control strategy can significantly enhance network coverage, reduce network energy consumption, and balance network energy consumption.

2. Problem Formulation

2.1. Problem Description

It is well known that wireless sensor network should be deployed with high density in order to improve coverage. Nodes self-organize to achieve a desired degree of coverage. The random deployment of sensors may lead to redundant nodes that sense the same area. If all sensor nodes simultaneously operate, redundant sensing data, corresponding wireless communication collision, and interference will cause much energy to be wasted. As the number of sensors deployed in target area is greater than the optimum needed to perform full coverage, an important energy-efficient method coverage solution is desired. Each sensor has two states: active or sleep. A sensor in active state consumes more energy than the sleep state. However, object sensing can be performed only in active state. Sizable energy savings can be achieved by using aggressive coverage control strategies in devising adaptive sleep schedules to minimize the amount of energy lost due to needless sense of redundant nodes. If a certain sense region of nodes can be completely covered by other nodes, this node is a redundant node and can be sleep. An important method for WSN coverage problem is to find the cover in sensors network. It is defined as a set of nodes that can completely cover target area. Therefore, in initial stage of the network, reasonable selection of nodes is important for network performance and operating costs. At the same time, balance consumption of network energy is crucial to stabilize operation of network and to extend lifetime of network. Thus, wireless sensor network coverage is a typical multi-objective optimization problem.

2.2. Network Model

Firstly, we assume that the target area is a two-dimensional rectangular region, and k sensors are randomly deployed in deployment stage. The binary sensor model [16] is shown in (1), expressing the coverage $p (i, j)$ of a grid point j by sensor i,

p (i, j) = {\begin{cases} 1 & if d_{i j} < r_{s}, \\ 0 & else, \end{cases}

(1)

d_{i j} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}} .

(2)

Sensor i is deployed at point $(x_{i}, y_{i})$ . For any point j at $(x_{j}, y_{j})$ , it is denoted the Euclidean distance between i and j as $d_{i j}$ . Each sensor has a detection range $r_{s}$ .

In other words, a point $(x_{j}, y_{j})$ is covered by a sensor i if its distance to the center $(x_{i}, y_{i})$ of the circle is less than the radius $r_{s}$ . It is assumed that the point $k (x, y)$ is covered by the node set if any node in the set covers it. As a result, the probability that the point $k (x, y)$ is covered by the node set can be denoted as the union of $P_{k}$ ,

P_{k} = 1 - \prod_{i = 1}^{N} (1 - p (i, k)) .

(3)

2.3. Mathematical Description of the Problem

We first define the terms in describing the local rule and the strategy. A is target region area. ${s_{1}, s_{2}, \dots, s_{l}}$ are sense areas of nodes in the active nodes set S, $0 \leq l \leq N$ . l is the number of working nodes, and N is the total number of nodes within the target region. The target area $A_{S}$ covered by the active node set S is defined as

A_{S} = \overset{l}{⋃_{i = 1}} s_{i} .

(4)

WSN node utilization ρ is defined as

ρ = \frac{l}{N} .

(5)

Definition 1 (regional energy $E Q_{k}$ ).

The monitored area is divided into K uniform grids, $k \in [1, K]$ . Then the kth grid regional energy equals to the ratio of total sum of the remaining energy of all nodes in the grid to the number of nodes

E Q_{k} = \frac{\sum_{i = 1}^{m_{k}} E_{k i}}{m_{k}},

(6)

where

m_{k}

is the number of kth grid nodes, and

E_{k i}

is the residual energy of nodes i in the kth-grid.

Definition 2 (energy-span $E s$ ).

The regional energy difference between the maximum and minimum values is divided by the maximum value of the regional energy. The divided result represents the energy span of current network

E s = \frac{Max (E Q_{k}) - Min (E Q_{k})}{Max (E Q_{k})} .

(7)

$E s$ represents the balance level of energy consumption for the whole network, and the higher value represents the more uneven network energy consumption. Therefore, the smaller value of $E s$ indicates the better network performance.

The contradictions, resulting from coverage control and algorithm running time, counterbalance each other. Regarding energy span and node utilization efficiency as optimization goal individually will increase complexity of algorithm. Meanwhile, equilibrium of network energy consumption is closely related with current node utilization. Therefore, in this paper, a linear weighted sum method that introduces energy consumption weight and energy balance weight is used to compromise on node utilization efficiency and energy span and make redundant nodes sleep to save energy on the basis of energy balance consumption. As a result, the optimization of active node set can be described as dual-objective optimization problem (DOP).

Object 1

Network coverage that is desirable to be maximized in the probability that the point of target region can be sensed is defined as

Max f_{A} (x) = \frac{A_{S}}{A} .

(8)

Object 2

Network equilibrium energy consumption that is desirable to be minimized in node utilization efficiency while considering energy balance consumption is defined as

Min f_{2} (x) = ω_{1} ρ + ω_{2} E s,

(9)

where

ω_{1}

is the energy consumption weight, and

ω_{2}

is the energy balance weight.

In order to minimize the two objectives simultaneously, the coverless is used as one of the fitness functions

Min f_{1} (x) = 1 - f_{A} (x) .

(10)

All in all, wireless sensor networks multi-objective coverage control model can be described as

\begin{matrix} Min & [f_{1} (x), f_{2} (x)] \\ s.t . & 0 \leq l \leq N, \\ x_{i} \in {0,1}, \\ 0 < k \leq K . \end{matrix}

(11)

3. Multiobjective Free Search Applied to WSN Coverage Control

A novel algorithm of swarm intelligence, free search (FS), is introduced, which is used to solve function optimization problems [17–19]. Considering aforementioned WSN network model, encoding rules and exploration strategy are improved to accommodate new design of the multi-objective free search algorithm.

3.1. Encoding Rules

As for the optimal sensor set selection in wireless sensor network, the solution is represented by a bit string N. Each individual sensor node is represented by a 1-bit binary number. The bit is used to describe the working state of the sensor node. Encoding defines the state of sensor nodes as follows: If it is equal to 1, the sensor is selected to be active, or else the sensor is unselected. Its encoding form is $x = (x_{1}, x_{2}, \dots, x_{i}, \dots, x_{N})$

x_{i} = {\begin{cases} 1, & sensor i is selected, \\ 0, & else . \end{cases}

(12)

Two examples of active node-set options are illustrated in Figure 1. As network nodes are randomly laid 8, the length of binary string is 8. As can be seen from Figure 1(a), network nodes (1, 3, 4, and 8) are active, and then the remaining nodes are on sleep state (redundant nodes); Figure 1(b) indicates that all nodes have been selected as working nodes, on active state.

Figure 1

Binary encoding structure of WSN.

3.2. Exploration Strategy

The original exploration walk generates coordinates of a new location $x_{t j i}$ as [17]

x_{t j i} = x_{0 j i} - Δ x_{t j i} + 2 Δ x_{t j i} \times {random}_{t j i} (0,1) .

(13)

The original modification strategy is

Δ x_{t j i} = R_{j i} (x_{i \max} - x_{i \min}) \times {random}_{t j i} (0,1),

(14)

where

i = 1

for unidimensional step, and

i = 1, \dots, n

for multidimensional step. T is step limit per walk. t is current step,

t = 1,2, \dots, T

R_{j i}

is variable neighbour space,

R_{j i} \in [R_{\min}, R_{\max}]

{Random}_{t j i} (0,1)

is a random value between 0 and 1.

For binary encoding rules and fitness function, we improve the evolution equations based on the above steps and select the suitable neighbour space (to be discussed in Section 4) to meet the requirements of the model.

The improved evolutionary equation is

x_{t j i} = round (x_{0 j i} - Δ x_{t j i} + 2 Δ x_{t j i} \times {random}_{t j i} (0,1)),

(15)

where

round (\cdot)

is the operator to round nearest integer.

3.3. Multiobjective Free Search Architecture

In [18, 19], the application of free search algorithm in the single-objective optimization is studied. A new multi-objective free search algorithm is designed for the aforementioned DOP, and its implementation is shown in Algorithm 1. The framework of MOFS developed by us is also fit for other combinatorial optimization problems.

Algorithm 1: Multi-objective free search algorithm.

Begin

initialise number of generation G, population size pop and individual step limit per walk T;

initialise $t = 1$ ;

generate an initial population randomly;

generate an archive arc randomly;

while ( $t < = G$ )

do {

$t = t + 1$ ;

for each individual i in pop

do{

select start locations for a walk;

take exploration walks;

assign fitness to individual i according to its position;

}

update the parent populations and the external archive;

record the best individual;

}

End

4. Simulation

The performance of multi-objective optimization coverage control strategy sections is given in this section. In particular, the performance of MOFS is discussed, and the parameters study is carried out. The simulation is conducted in MATLAB.

4.1. Effectiveness of MOFS

First of all, multi-objective traveling salesman examples are used to verify the validity of the algorithm, and the performance was compared with a few important previous works’ algorithms. It can lay a good foundation for WSN application.

Multi-objective traveling salesman problem (MOTSP) is a classic multi-objective optimization problem [20], which can be described as follow: there are N cities, and each path between two cities has L indicators; the problem is finding a best close route passing through all the cities and once for each city, while making a balance with L indicators of the route. For instance, it requires to select a best route with the shortest distance, the minimum risk, the least time and cost, and so on. The set of all solutions satisfying the above condition is named Pareto set. Thus, MOFS can be a powerful tool to solve MOTSP.

The mathematical model of MOTSP can be stated as follows: given a weighted graph $W = (V, E)$ , where V is a set of vertexes $| V | = n$ , E is the set of edges, $w_{i j}$ is the cost between vertexes i and j such as time and distance. We assume that

x_{i j} = {\begin{cases} 1 & if the edge between i and j is selected, \\ 0 & otherwise . \end{cases}

(16)

Objective function can be described as

\min f (x) = F (f_{1}, f_{2}, \dots, f_{R}) .

(17)

Constraints can be described as

\begin{gathered} f_{r} = \sum_{i = 1}^{N} \sum_{j = 1}^{N} w_{i j} \cdot x_{i j} 1 \leq r \leq R, \\ \sum_{i \neq j} w_{i j} = 1, \\ \sum_{i \neq j} s \cdot x_{i j} \leq | s | - 1, \\ x_{i j} > 0, x_{i j} = + \infty, \end{gathered}

(18)

where s is the subset of V, and

| s |

is the elements number of s.

An example from reference [21] was used to quantify the efficiency of the algorithm. There are 6 cities in this example; the distance value matrix $D_{1}$ and the cost value matrix $D_{2}$ are shown as follows:

\begin{gathered} D_{1} = [\begin{bmatrix} \infty & 81 & 72 & 55 & 81 & 3 \\ 81 & \infty & 3 & 44 & 9 & 40 \\ 72 & 3 & \infty & 87 & 77 & 21 \\ 55 & 44 & 87 & \infty & 67 & 25 \\ 81 & 9 & 77 & 67 & \infty & 93 \\ 3 & 40 & 21 & 25 & 93 & \infty \end{bmatrix}], \\ D_{2} = [\begin{bmatrix} \infty & 82 & 14 & 14 & 43 & 47 \\ 82 & \infty & 61 & 76 & 29 & 47 \\ 14 & 61 & \infty & 29 & 31 & 51 \\ 14 & 76 & 29 & \infty & 78 & 67 \\ 43 & 29 & 31 & 78 & \infty & 28 \\ 47 & 47 & 51 & 67 & 28 & \infty \end{bmatrix}] . \end{gathered}

(19)

MOFS parameter settings were as follows: individual step limit per walk T was 10, population size $p o p$ was 100, and the number of iterations G was 100.

Pareto front obtained by MOFS is shown in Figure 2. Result is consistent with [21], the shortest distance is 158, and the least cost is 197. Then, (158, 197) is the ideal solution according to the definition. Thus, (158, 280) in the archive is the current optimal solution, because it has a minimum deviation of 0.4213 with the ideal solution.

Figure 2

Pareto front obtained by MOFS.

Pareto front obtained by MOFS was compared with Ant colony algorithm (Ant cycle, Ant density, and Ant quantity), simulated annealing algorithm(SA), and 2-opt algorithm in [21]. The algorithm performance is shown in Table 1. It can be observed that there are many more nondominated solutions in Pareto front with MOFS, and the convergence situation is better.

Table 1

Multi-objective TSP simulation results.

MOFS	Ant cycle	Ant density	Ant quantity	SA	2-opt
(271,197)	(158,280)	(158,280)	(158,280)	(209,248)	(158,280)
(250,208)	(250,208)	(250,208)	(208,276)	(158,280)
(209,248)				(250,208)
(194,265)
(158,280)

These results show that MOFS can effectively solve multi-objective combinatorial optimization problems. And compared with the traditional multi-objective algorithm, MOFS can achieve better performance.

4.2. Effect of Parameter on Performance

In this section, the parameters study is carried out, and their effect on the performance is discussed. We studied the effect of variable $R_{j i}$ and given a preferable selection scheme of weights.

4.2.1. Selection of Variable Neighbour Space

We studied the effect of variable neighbour space $R_{j i}$ on WSN node utilization $(ρ)$ and network coverage $(f_{1})$ described in Section 2.3 when $R_{j i}$ varies from 0.7 to 9. Other parameters of MOFS were the same as simulation in Section 4.1.

WSN configuration was assumed: target area was 100 m × 100 m rectangular area, 196 sensor nodes were planted in this region with grid topology, and the distance between two neighbor nodes was 7 m. All the used nodes were the same type. Coverage area of each sensor was a circle of radius $r_{s} = 10 m$ . All nodes were static once they were deployed.

Pareto front under different neighbour space $R_{j i}$ is shown in Figure 3. The value of $R_{j i}$ is fixed to observe the changes of Pareto front. It is found that global convergence results increase with the increment of $R_{j i}$ from 0.7 to 5. The algorithm finds few nondominated solutions when $R_{j i} = 0.7$ , and the distribution is uneven; when $R_{j i} = 1$ , the distribution of individuals is more even, and the convergence is better. Pareto front has significantly improved when $R_{j i} = 5$ , and the global convergence situation is better. This indicates that $R_{j i}$ can be used to control convergence. Larger value of $R_{j i}$ can enhance the capacity of global search algorithm, while the smaller value is used for the local search. Therefore, the value of $R_{j i}$ is a variable in search process. We take a larger value to get more nondominated solutions in search early stage and a smaller value to obtain better convergence in the latter stages of search. As shown in Figure 3(d), the larger value of $R_{j i}$ did not represent the better global search result, the result will not be obviously improved with too large value.

Figure 3

Pareto front under a different $R_{j i}$ . (a) When $R_{j i} = 0.7$ . (b) When $R_{j i} = 1$ . (c) When $R_{j i} = 5$ . (d) When $R_{j i} = 9$ .

Next, setting neighbour space was variable, and initial $R_{j i}$ was 10. And with the algorithm running, $R_{j i}$ became small gradually. Pareto front under variable neighbour space $R_{j i}$ is shown in Figure 4. As compared with Figure 3, it can be found that the results have been improved significantly. For example, the convergence results become well, and the number of archives increases slightly. Simulation shows that the appropriate $R_{j i}$ is an important contribution to the optimization results. Therefore, we explore multi-objective optimization coverage control strategy that uses a variable $R_{j i}$ in the following simulations.

Figure 4

Pareto front under a different $R_{j i}$ .

4.2.2. Selection of Weights

The choice of weight is reasonable or not can affect the performance of coverage control strategies. For practical problems, different selection of weight can meet various business requirements. The simulation comparisons for different weight option will be discussed as follows.

The initial $R_{j i}$ of MOFS was 10, and the algorithm ran 100 generations. To investigate the relationship between network energy consumption and energy balance, we used different energy consumption weight and energy balance weight while keeping the other parameters constant. We also independently repeated experiments to explore the effect of different proportion of weights on network coverage and the number of active nodes.

Table 2 shows the network coverage $(F_{1})$ and the number of active nodes $(F_{2})$ that come from the algorithm, which are based on different choices of weight for different coverage threshold. Different weight ratio means the different compromise level on the number of network nodes and network energy consumption. $ω_{1} = 1$ and $ω_{2} = 0$ mean that we donot take the balance of energy consumption into account and just regard node utilization as fitness function to find the minimum network energy consumption. Therefore, as shown in the table, the number of used network nodes is the least under above parameters. Simulation results show that if $ω_{2}$ is too large, which means too much attention to energy consumption balance as well as ignoring the importance of utilization of the node, this will result in the increase of the number of work nodes and the decrease of the performance of control strategies. According to a large number of experiments, $ω_{1} = 0.7$ and $ω_{2} = 0.3$ are chosen as parameters to achieve better coverage control effect in this WSN application.

Table 2

Network coverage and the number of active nodes with different weights $(F_{1} / F_{2})$ .

$ω_{1}$ energy consumption weight, $ω_{2}$ energy balance weight		Coverage thresholds
		80.00%	85.00%	90.00%	95.00%	100.00%

$ω_{1} = 0.5$ , $ω_{2} = 0.5$	F₁	85.49%	85.49%	90.25%	94.56%	99.77%
$ω_{1} = 0.5$ , $ω_{2} = 0.5$	F₂	63	63	70	76	150

$ω_{1} = 0.7$ , $ω_{2} = 0.3$	F₁	79.37%	83.22%	92.06%	94.56%	99.77%
$ω_{1} = 0.7$ , $ω_{2} = 0.3$	F₂	43	53	73	80	130

$ω_{1} = 1$ , $ω_{2} = 0$	F₁	79.59%	83.90%	90.48%	94.78%	99.77%
$ω_{1} = 1$ , $ω_{2} = 0$	F₂	42	48	62	73	119

4.3. Performance of Multiobjective Coverage Control Strategy

In this section, network coverage and network equilibrium energy consumption tradeoff provided by multi-objective coverage control strategy are studied. Network coverage $(f_{1})$ and network equilibrium energy consumption $(f_{2})$ are described for the fitness function in Section 2.3.

The target area was 100 m × 100 m, and plant 200 sensor nodes were randomly and evenly distributed, and $r_{s} = 10 m$ . Since the relationship of coverage and connectivity has been proved in [22], the transmission range of sensor nodes was assumed to be at least twice the sensing range, and then network is well connected.

MOFS's initial $R_{j i}$ was 10, the algorithm ran 100 generations, energy consumption weight $ω_{1} = 0.7$ , and energy balance weight $ω_{2} = 0.3$ .

In the cover control simulations (Figure 5), we select nondominated solutions in Pareto solution set and plot curves, respectively, to observe the coverage and the number of active nodes. It can be seen from Figure 5(b) that there are a large number of redundant nodes in initial random network, and the initial coverage is 99.77% in 200 nodes network. In Figure 5(d), the utilization of 67 nodes obtain 93.65% network coverage in the 50th generation of algorithm (the blue part in the figure indicates the region not covered). Because of our strategy taking equilibrium of network energy consumption into account, the least active nodes number is not the best. When the algorithm runs to 100th generation, the use of 73 nodes can guarantee 92.06% network coverage, and the active nodes are distributed more evenly.

Figure 5

Multi-objective optimization coverage control experiment of WSN. (a) The initial distribution of 200 nodes. (b) The initial coverage of 200 nodes is 99.77%. (c) The 10th generation, coverage of 101 nodes is 97.96%. (d) The 50th generation, coverage of 67 nodes is 93.65%. (e) The 100th generation, coverage of 73 nodes is 92.06%.

For different business requirements, WSN network needs to achieve different monitoring coverage rate. The partial coverage problem is that the users assign the preset coverage threshold based on the actual business requirements. In most cases, partial cover can meet the business requirements and need fewer work nodes. At the same time, network energy consumption becomes smaller, so the network lifetime is extended. Since the coverage control strategy by MOFS is able to generate a set of Pareto-optimal designs, the system designers will have more freedoms to make a reasonable tradeoff from the set of Pareto-optimal solutions according to their preferences or operation requirements. Network coverage situation with MOFS is shown in Figure 6 when coverage threshold is 80%, 85%, 90%, 95%, and 100%, respectively. Each option is the nondominated solution that is the closest coverage to the preset threshold in Pareto solution set.

Figure 6

Coverage and number of active nodes under different preset coverage threshold. (a) Coverage 79.37%, 43 nodes. (b) Coverage 83.22%, 53 nodes. (c) Coverage 92.06%, 73 nodes. (d) Coverage 94.56%, 80 nodes. (e) Coverage 99.77%, 130 nodes.

These results show that the coverage control strategy can effectively reduce the use of redundant nodes to decrease overall network energy consumption based on the balance consumption of energy.

5. Conclusions

In this paper, an energy-balanced consumption coverage control strategy based on multi-objective optimization is presented. The strategy is used to compromise on coverage, energy, and energy equilibrium degree by MOFS algorithm to determine the working status of sensor nodes. Meanwhile, the proposed strategy can adjust weight and coverage threshold to obtain the optimum allocation of different business requirement and then to improve the applicability of WSN network. It is obvious that the coverage control strategy has wide applicability, and the effectiveness of the strategy is verified by the simulated results.

Footnotes

Acknowledgments

This work has been supported by the National Natural Science Foundation of China (no. 60901041), the Science and Technology Project of Nantong University (no. 09ZW001), and the Nantong Application Research Project (no. K2010015).

References

Cardei

D. Z.

Improving wireless sensor network lifetime through power aware organization

Wireless Networks 2005 11 3 333 340

2-s2.0-24044520078

10.1007/s11276-005-6615-6

J. Z.

J. B.

Shi

S. F.

Concepts, issues and advance of sensor networks and data management of sensor networks

Journal of Software 2003 14 10 1717 1727

2-s2.0-1442327624

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 105

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Cardei

Energy-efficient coverage problems in wireless ad-hoc sensor networks

Computer Communications 2006 29 4 413 420

2-s2.0-32644446747

10.1016/j.comcom.2004.12.025

Zhong

Cheng

Zhang

PEAS: a robust energy conserving protocol for long-lived sensor networks

Proceedings of the International Conference on Distributed Computing Systems

2003

Providence, RI, USA

28 37

Abrams

Goel

Plotkin

Set K-cover algorithms for energy efficient monitoring in wireless sensor networks

Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04)

2004

Berkeley, Calif, USA

424 432

Tian

Georganas

N. D.

A node scheduling scheme for energy conservation in large wireless sensor networks

Wireless Communications and Mobile Computing 2003 3 2 271 290

2-s2.0-3042738623

10.1002/wcm.116

Chakrabarty

Iyengar

S. S.

Cho

Grid coverage for surveillance and target location in distributed sensor networks

IEEE Transactions on Computers 2002 51 12 1448 1453

2-s2.0-0036933529

10.1109/TC.2002.1146711

Wang

Kulkarni

S. S.

Sacrificing a little coverage can substantially increase network lifetime

Ad Hoc Networks 2008 6 8 1281 1300

2-s2.0-49949118647

10.1016/j.adhoc.2007.11.013

10.

Meguerdichian

Koushanfar

Potkonjak

Srivastava

M. B.

Coverage problems in wireless ad-hoc sensor networks

Proceedings 20th Annual Joint Conference of the IEEE Computer and Communications Societies

2001

Anchorage, Alaska, USA

1380 1387

11.

Habib

S. J.

Modeling and simulating coverage in sensor networks

Computer Communications 2007 30 5 1029 1035

2-s2.0-33847082151

10.1016/j.comcom.2006.08.026

12.

Wang

Parallel energy-efficient coverage optimization with maximum entropy clustering in wireless sensor networks

Journal of Parallel and Distributed Computing 2009 69 10 838 847

2-s2.0-68849112923

10.1016/j.jpdc.2009.04.012

13.

Youssef

S. M.

Hamza

M. A.

Fayed

S. F.

EQOWSN: evolutionary-based query optimization over self-organized wireless sensor networks

Expert Systems with Applications 2009 36 1 81 92

2-s2.0-53849117112

10.1016/j.eswa.2007.09.062

14.

Jia

Chen

Chang

Tan

Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm

Computers and Mathematics with Applications 2009 57 11-12 1756 1766

2-s2.0-67349235580

10.1016/j.camwa.2008.10.036

15.

Martins

F. V. C.

Carrano

E. G.

Wanner

E. F.

Takahashi

R. H. C.

Mateus

G. R.

A dynamic multiobjective hybrid approach for designing wireless sensor networks

Proceedings of the IEEE Congress on Evolutionary Computation (CEC '09)

May 2009

1145 1152

2-s2.0-70449786584

10.1109/CEC.2009.4983075

16.

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS '00)

2000

Maui, Hawaii, USA

223

17.

Penev

Littlefair

Free search—a comparative analysis

Information Sciences 2005 172 1-2 173 193

2-s2.0-18144378777

10.1016/j.ins.2004.09.001

18.

Zhou

A novel swarm intelligent algorithm—free search

Journal of DongHua University 2007 33 579 583

19.

Zhou

D. M.

Shao

S. H.

Yuan

C. M.

Novel swarm intelligence algorithm and its improvement

Systems Engineering and Electronics 2008 30 2 337 340

2-s2.0-41349105922

20.

Bektas

The multiple traveling salesman problem: an overview of formulations and solution procedures

Omega 2006 34 3 209 219

2-s2.0-27744588516

10.1016/j.omega.2004.10.004

21.

Jiang

Solving multi-criteria traveling salesman problem by ant algorithm

System Engineering Theory Methodology Applications 1999 8 23 27

22.

Zhang

Hou

J. C.

Maintaining sensing coverage and connectivity in large sensor networks

Ad-Hoc and Sensor Wireless Networks 2005 1 89 124

Multiobjective Coverage Control Strategy for Energy-Efficient Wireless Sensor Networks

Abstract

1. Introduction

2. Problem Formulation

2.1. Problem Description

2.2. Network Model

2.3. Mathematical Description of the Problem

Definition 1 (regional energy E Q k ).

Definition 2 (energy-span E s ).

Object 1

Object 2

3. Multiobjective Free Search Applied to WSN Coverage Control

3.1. Encoding Rules

3.2. Exploration Strategy

3.3. Multiobjective Free Search Architecture

Algorithm 1: Multi-objective free search algorithm.

4. Simulation

4.1. Effectiveness of MOFS

4.2. Effect of Parameter on Performance

4.2.1. Selection of Variable Neighbour Space

4.2.2. Selection of Weights

4.3. Performance of Multiobjective Coverage Control Strategy

5. Conclusions

Footnotes

Acknowledgments

References

Definition 1 (regional energy $E Q_{k}$ ).

Definition 2 (energy-span $E s$ ).