Information Sciences 180 (2010) 4818–4833

Contents lists available at ScienceDirect

Information Sciences
journal homepage: www.elsevier.com/locate/ins

A memetic algorithm for extending wireless sensor network lifetime
Chuan-Kang Ting ⇑, Chien-Chih Liao
Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi 62102, Taiwan

a r t i c l e

i n f oArticle history:
Received 8 September 2009
Received in revised form 5 June 2010
Accepted 14 August 2010

Keywords:
Memetic algorithm
Evolutionary algorithm
Wireless sensor network
Lifetime extensiona b s t r a c t
Extending the lifetime during which a wireless sensor network (WSN) can cover all targets
is a key issue in WSN applications such as surveillance. One effective method is to partition
the collection of sensors into several covers, each of which must include all targets, andthen to activate these covers one by one. Therefore, more covers enable longer lifetime.
The problem of ﬁnding the maximum number of covers has been modeled as the SET
K-COVER problem, which has been proven to be NP-complete. This study proposes amemetic algorithm to solve this problem. The memetic algorithm utilizes the Darwinianevolutionary scheme and Lamarckian local enhancement to search for optima given theconsiderations of global exploration and local exploitation. Additionally, the proposed
algorithm does not require an upper bound or any assumption about the maximum
number of covers. The simulation results on numerous problem instances conﬁrm thatthe algorithm signiﬁcantly outperforms several heuristic and evolutionary algorithms interms of solution quality, which demonstrate the effectiveness of the proposed algorithm
in extending WSN lifetime.
Ó 2010 Elsevier Inc. All rights reserved.

1. Introduction
Recent advances in hardware miniaturization, communication technologies, and low-cost mass production have facilitated the emergence of wireless sensor networks (WSNs) that consist of small, inexpensive, battery-powered, and wirelessly
connected sensors. The WSNs have brought up various new applications, including surveillance, home security, and environmental monitoring [3,4,25,42]. WSN sensors are deployed randomly or systematically to collect information about their surroundings within their sensing range. They can transmit the collected information via wireless communication; some caneven process the data before transmission. Despite their widely varying characteristics, all sensors essentially collect, transmit, and relay information. A promising WSN application is long-term surveillance in hostile or distant environments. Using
WSNs for military surveillance, for example, involves deploying numerous sensors throughout the region of interest by aircraft to detect enemy activity or equipment. However, a key consideration in the design of WSNs is the power supply since
replacing batteries in sensors is often impractical.
Although a considerable number of studies have addressed energy efﬁciency issues in generic wireless ad hoc networks,
distributed sensing applications impose new constraints on sensor network coverage [10]. For instance, surveillance applications may require at least one sensor in each location in a geographic region of interest [8], while object tracking applications may require at least three sensors [7]. Data sampling applications may require coverage of a given percentage ofmonitored regions. In addition to sensing coverage, network connectivity is another important property of WSNs. Connectivity enables sensor nodes to relay collected information back to data sinks. Zhang and Hou [45] proved that if the communication range is at least twice the sensing range, then full coverage of a convex area implies connectivity of the WSN. Hence,⇑ Corresponding author.
E-mail addresses: ckting@cs.ccu.edu.tw (C.-K. Ting), lcch97p@cs.ccu.edu.tw (C.-C. Liao).
0020-0255/$ - see front matter Ó 2010 Elsevier Inc. All rights reserved.
doi:10.1016/j.ins.2010.08.021

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

4819

the constraints of full coverage and connectivity can be reduced to the full coverage constraint alone. This study adopts thisresult and therefore considers the full coverage constraint. The WSN lifetime is accordingly deﬁned as the time span during
which a WSN satisﬁes the full coverage constraint.
Scheduling sensor activity is an important approach for prolonging WSN lifetime. It involves the scheduling of sensors toalternate between active and inactive modes so that they can maintain coverage with reduced power requirements [34,36].
More speciﬁcally, this approach divides all sensors into disjoint sensor subsets, or sensor covers,1 each of which must satisfy
the full coverage constraint. At any time, only one sensor cover in active mode provides functionality, while the remaining sensor covers stay inactive to save energy. Once any sensor in the active sensor cover runs out of energy and thus cannot maintainfull coverage, one of the inactive sensor covers is selected to enter active mode and continue the functionality. Therefore, identifying more sensor covers allows the WSN lifetime to be extended further. Recent studies [34,40] indicate that this approach
not only reduces energy consumption, but also prolongs sensor network lifetime.
The problem of ﬁnding the maximum number of covers to extend WSN lifetime has been modeled as the SET K-COVER
problem [38]. Provided K covers, the lifetime of WSNs can ideally be extended by a factor of K using the above approach under the coverage constraint. The SET K-COVER problem has been proven to be NP-complete. Under the assumption NP – P,
no exact algorithm can solve this problem in polynomial time. Some heuristic algorithms have been presented, but they generally suffer from the trade-off between solution quality and running time. Recently, Lai et al. [23] proposed using genetic
algorithm (GA) to deal with this trade-off. The GA achieves near-optimal solutions in acceptable time but requires information on the value of K or its upper bound, which is usually unobtainable. Additionally, such approaches rarely yield optimal
solutions. A means of improving solution quality with a short running time is urgently needed.
This study develops a memetic algorithm (MA) to solve the SET K-COVER problem of extending WSN lifetime. Memetic
algorithm is a blooming dialect of evolutionary algorithm (EA). In addition to Darwinism, MA adopts the Lamarckian theory
that offspring can inherit the knowledge or characteristics that their parents acquire during their lifetime. The MA implements this idea by integrating a local enhancement, such as local search and repair operator, into the canonical EA, and making the enhancement inheritable. This integration signiﬁcantly improves the exploitation ability of EA and has been widely
shown to provide superior solution quality and high convergence speed [16,21,24,27,31–33,37]. The proposed MA is basedon the order-based GA with the compact operator, which is a novel local enhancement operator that is designed to address
the SET K-COVER problem. Furthermore, this study devises a ﬁtness function based on the contribution of sensors to covers.
A series of simulations is conducted to evaluate the performance of the proposed MA in terms of solution quality and runningtime, and to verify its superiority over several heuristic and evolutionary algorithms.
The rest of this paper is organized as follows. Section 2 reviews related work on WSN lifetime extension. Section 3 formulates the problem of extending the WSN lifetime. Section 4 sheds light on the proposed MA and its operators. Simulation
results are presented in Section 5. Finally, conclusions are drawn in Section 6.

2. Related work
The many aspects of the WSN lifetime problem include sensor activity scheduling [8,38], network structure [7], data
aggregation [17,20,22], data compression [26], and routing protocol [18,29,35]. (For a complete survey, see [3]). This study
focuses on sensor activity scheduling. The problem of extending WSN lifetime by sensor activity scheduling was ﬁrst modeled as the SET K-COVER problem by Slijepcevic and Potkonjak [38]. They proved the NP-completeness of this problem byreduction from the minimum cover problem [13]. To solve this problem, the authors proposed the most constrainedminimally constraining covering heuristic (MCMCC). This approach runs in polynomial time but often yields unsatisfactory
results. Cardei and Du [8] formulated WSN lifetime extension as the disjoint set covers (DSC) problem, which is analogous to
the SET K-COVER problem. They presented a heuristic algorithm, called maximum covers using mixed integer programming(MCMIP), to solve the DSC problem. Although the MCMIP method can ﬁnd the optimal solution, its implicit exhaustive searchrequires exponential running time. This high computational cost limits its applicability for large-scale WSNs. Cardei et al. [9]further considered cases without the disjointedness constraint on sensor subsets. Additionally, Berman et al. [5] took the initial battery power and energy consumption rate into account. In their study, the constraint on disjointedness is relaxed sothat each sensor can participate in different sensor covers as long as it still has energy. The authors designated this problem
the sensor network lifetime problem (SNLP), which entails ﬁnding a monitoring schedule that maximizes the network lifetime. They developed a (1 + ln (1  q)1)-approximation algorithm for the case in which a q-portion of the monitored area
must be covered. To cover 95% of the monitored area, for example, their schedule ensures that the obtained lifetime is at
most 3.99 times shorter than the optimal lifetime.
Instead of maximizing lifetime, Abrams et al. [1] formulated the problem of ﬁnding the maximum average coverage given
the number of covers. They claimed that this problem is more natural than the SET K-COVER problem in that full coverage isless likely to be achieved when sensors are distributed randomly and heterogeneously. The authors devised three algorithms
to solve this problem. The ﬁrst is a randomized algorithm with an expected fraction 1  1e of the optimum. The second is a
distributed greedy algorithm with a 12-approximation ratio. The third is a centralized greedy algorithm, which is a derandomized version of the ﬁrst algorithm and has a ð1  1e Þ-approximation ratio. Ai et al. [2] viewed the relationship between
1

In this paper, the two terms ‘sensor cover’ and ‘cover’ are used interchangeably.

4820

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

this problem and the optimal solutions as an approximate Nash equilibrium for graphical games. Their proposed DRACo
method achieves near-optimal coverage on test problems.
The above approaches for extending WSN lifetime, however, suffer from the trade-off between solution quality and running time. For the SET K-COVER problem, the MCMCC takes only polynomial time but often yields unsatisfactory solutions.
On the other hand, the MCMIP ensures optimal solutions but at the cost of exponential time complexity. To address this issue, Lai et al. [23] designed an integer-coded GA in which a gene ci 2 N indicates the group number assigned to sensor Si, anda chromosome represents the group arrangement of all sensors for covers. In the course of evolution, the groups graduallyform covers, i.e., they satisfy the constraint of full coverage. Studies have demonstrated that this algorithm outperforms
MCMCC in terms of the number of covers and is much faster than MCMIP. Nevertheless, one defect is that, owing to the integer representation of chromosomes, this GA requires an upper bound on the number of covers, which is usually unobtainable. Moreover, like most other GAs, the proposed GA rarely yields optimal solutions. Therefore, an algorithm is still needed
to consistently deliver, within an acceptable running time, good activity schedules for extending WSN lifetime.
3. Problem formulation
This study addresses the SET K-COVER problem of WSN lifetime extension. Suppose n sensors S1, . . . , Sn are deployed tomonitor m targets T1, . . . , Tm. A target Tj is said to be covered if it lies within the sensing range of at least one sensor. Fig. 1
shows a WSN with ﬁve sensors and four targets. The relationship between sensors S1, . . . , S5 and targets T1, . . . , T4 is represented by a bipartite graph G = (V, E), where V = S [ T and eij 2 E if Si covers Tj. Fig. 2 presents the bipartite graph of the WSN in
Fig. 1, where S1 = {T1}, S2 = {T1, T2}, S3 = {T2, T3, T4}, S4 = {T3}, and S5 = {T4}. The maximum number K of disjoint covers in thisexample is two. They are C1 = {S1, S3} and C2 = {S2, S4, S5}.
The SET K-COVER problem is to ﬁnd the maximum number of covers associated with the longest lifetime extension,
which is equivalent to partitioning the set of sensors into the maximum number of covers. The problem is deﬁned formallybelow.
Deﬁnition (SET K-COVER Problem). Given a collection S = {S1, . . . , Sn} of subsets of a ﬁnite set T = {T1, . . . , Tm}, ﬁnd the
maximum number, K, of covers C1, . . . , CK # S with Ci \ Cj = ; for i – j, such that every element of T belongs to at least one
element of Ci.
This problem has been proven to be NP-complete [38]. Cardei and Du [8] also presented an equivalent formulation as the
disjoint set covers (DSC) problem and proved its NP-completeness. This problem has been applied not only to extension of
WSN lifetime, but also to protein and gene networks [6] and database systems [44].
4. Proposed memetic algorithm
This work proposes a novel MA to solve the SET K-COVER problem of maximizing WSN lifetime. The MA implements the
GA scheme and additionally adopts the compact operator, which is a local enhancement operator that is designed speciﬁcallyfor the SET K-COVER problem. Algorithm 1 presents the framework of the proposed MA. Following the GA scheme, the MA
encodes candidate solutions as chromosomes. The method of encoding chromosomes is referred to as representation, which isessentially related to the problem to be solved. The ﬁtness function evaluates the quality (ﬁtness) of candidate solutions(chromosomes). In maximization problems, a better solution corresponds to higher ﬁtness. The EAs, such as GA and MA,
manipulate a set (population) of chromosomes to search for the optimal solution.

S4

S1

T3

T1

S2

S3
T4

T2

S5

Fig. 1. Example deployment of WSN.

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

S1

S3

S2

T1

T2

S4

T3

4821

S5

T4

Fig. 2. Bipartite graph of a WSN.

Algorithm 1. Memetic algorithm
initialize population P;
evaluate P;
while (not terminated){
Ps = Select (P);Pc = Crossover (Ps);Pm = Mutate (Pc);
P0 = LocalEnhance (Pm);evaluate P0 ;P = Survival (P, P0 );};After initializing the population, MA embarks on the evolutionary process. First, the selection operator picks two chromosomes from the population to serve as parents. The crossover operator then exchanges the information between these twoparents to produce their offspring. A predetermined crossover rate deﬁnes the probability of performing crossover. Analogously, mutation is performed with a probability, called mutation rate, to alter slightly some genes in the offspring. This
study develops the compact operator as a local enhancement operator for the MA to deal with the SET K-COVER problem.
This operator is applied to the offspring after the mutation phase.
The process of reproduction, selection–crossover–mutation–compact, is repeated until the offspring population is ﬁlled.
Based on the Darwinian theory of ‘‘Survival of the Fittest”, the survivor operator selects the ﬁttest chromosomes from theoffspring population with or without the parental population. The selected chromosomes constitute the next-generation
population. As the evolution continues, the MA is expected to drive the search toward the global optima. The following subsections describe the elements of the proposed MA in further detail.
4.1. Representation
This study proposes the use of an order-based representation for chromosomes. In the SET K-COVER problem, partitioning
the set of sensors into subsets for covers can be conceptualized as a process of accumulating covers. Accordingly, a gene ci at
locus i indicates that sensor Sci is collected in the ith order; a chromosome represents the sequence in which all sensors arecollected to form covers. As Fig. 3 shows, S3 initializes the ﬁrst group G1. When S1 joins this group, it forms a cover since

3 1

4 5 2

S1

S2

S3

S4

S5

2

5

1

3

4

T1

T2

T3

T4

Fig. 3. Order-based chromosome. The number in the circle of sensor node Si denotes the order in which Si is collected.

4822

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

group G1 = {S3, S1} includes all elements of T. Next, S4 participates in a new group for another cover. This accumulative processcontinues until all sensors have been distributed to groups in order—the number of accumulated covers is therefore the number K of disjoint covers to be maximized. Like the integer representation used in [23], the order-based representation always
satisﬁes the ‘‘disjointedness” of covers, in that each gene appears exactly once and can join only one group (cover). Moreover,a major advantage of the order-based representation is that, unlike integer representation, no upper bound or assumed number K is required.
4.2. Fitness function
The ﬁtness function is vitally important to EAs because it explicitly or implicitly affects the search direction. An effectiveﬁtness function must render sufﬁcient information about the search direction and clearly distinguish between good and bad
candidate solutions. The ﬁtness function is essentially problem-dependent. A ﬁtness function for the SET K-COVER problem
can simply treat the number of covers as the ﬁtness value. Although this method has proven effective in integer-coded GA[23], it does not account for groups that include several sensors covering the same targets. This redundancy potentiallyreduces the number of obtained covers.
This study addresses this issue by considering how each sensor ‘contributes’ to a cover. More speciﬁcally, the ﬁtness valueof a chromosome is deﬁned as the sum of contributions of all sensors, where the contribution of a sensor is quantiﬁed as theincremental change in the number of covers to which the sensor leads. For example, in the left part of Fig. 4, the contributionof S3 is three, and that of S5 is zero. Notably, the contribution of S2 is two, since it covers two targets (T1 and T2) for a newgroup G2. The ﬁtness value of the chromosome is therefore 3 + 0 + 0 + 1 + 2 = 6. The proposed ﬁtness function can distinguishbetween whether a sensor is contributive or redundant to the formation of a cover. This distinction regarding ﬁtness helps indirecting the evolutionary search. Section 5 will further examine the advantage of this ﬁtness function.
Incidentally, the number of covers can be simply obtained by bf(c)/jTjc, where f(c) denotes the ﬁtness of chromosome c.
For instance, the chromosome in the left part of Fig. 4 has b6/4c = 1 cover.
4.3. Selection
The selection operators, including parent selection and survivor selection, follow the Darwinian principle of survival of the
ﬁttest. First, parent selection is ordinarily based on an alternative explanation of natural selection: ﬁtter individuals shouldhave a higher probability of reproducing. A common implementation of this principle is ﬁtness-proportionate selection. Thismethod is also called roulette wheel selection because it selects parents in a manner analogous to the spinning of a roulette
wheel, in which the size of a pocket is proportional to the ﬁtness of an individual. Its main drawbacks are its need for global
ﬁtness information and its sensitivity to the distribution of ﬁtness in the population. The k-tournament selection eliminates
these drawbacks by choosing the winner among k individuals that are drawn randomly from the population. The number kcontrols selection pressure: a higher k gives higher selection pressure.
Second, survivor selection genuinely applies the principle of survivor of the ﬁttest. Only the ﬁttest individuals are selected
as parents for the next-generation. The methods of survivor selection can be classiﬁed according to the number of parents
who compete for survival. The (l + k) survivor selection merges the parental and the offspring populations to compete forsurvival.
The proposed MA is not subject to selection operators: any GA selection operator can be applied to the MA. This study adopts
tournament parent selection and (l + k) survivor selection in experiments because of their recognized good performance.
4.4. Crossover and mutation
The crossover of order-based chromosomes requires a special design to ensure the legality of an order, i.e., containing no
duplicate numbers in an order. Various crossover operators have been proposed for order-based representation. These

3 5

4 1 2

3 1

2 5 4

S2

S3

compact

S1

T1

S2

T2

S3

S4

S5

T3

T4

S1

T1

T2

Fig. 4. Example of compact operation.

S4

S5

T3

T4

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

4823

operators generally explore the relationships between the two parental orders and then use this information to generate
legal orders. The two main relationships involved are mapping and adjacency. The mapping operation establishes a correspondence of genes at the same locus between parents in the crossover phase. The crossover operators using this technique
include the well-known partially mapped crossover (PMX) [15], order crossover (OX) [11], and cycle crossover (CX) [30]. The
adjacency information, however, is essential in combinatorial problems such as the traveling salesman problem (TSP). Crossover operators that adopt this information, such as the series of edge recombinations [28,39,41,43], are widely used to tackle
the TSP, although they are applicable to other combinatorial problems.
The mutation of order-based representation also requires order legality. The bitwise and gene-wise mutation operators
cannot fulﬁll this requirement since a legal move requires a change in at least two genes. Several mutation operators fororder-based representation, e.g., swap, insertion, scramble, and inversion, have been proposed to deal with the issue of order
legality [12,14].
Any order-based crossover and mutation is applicable to the proposed MA. However, the crossover operators that focus
on mapping relationships are preferred because the key information required for solving the SET K-COVER problem is theorder of collecting sensors rather than adjacency. In the light of its virtue in preserving relative order, order crossover fororder-based EAs is utilized herein. The widely used swap mutation is applied in the experiments. Additionally, an alternative
deﬁnition [19] of mutation rate is employed. The original mutation rate for order-based representation is deﬁned as theprobability that a chromosome mutates once. Even the highest mutation rate 1.0 can result in only one swap in a chromosome, severely restricting the extent of mutation. To increase the extent of mutation, a Poisson-distributed random generator is adopted to determine the number of swaps needed to mutate a chromosome, where the mutation rate is given by theparameter k in the Poisson distribution. Therefore, the number of swaps in a chromosome can exceed one to increase
diversity.
4.5. Compact operator
In the proposed MA, sensor order is key to the cover collection process. A cover that contains redundant sensors inhibits
from using them subsequently and therefore reduces the opportunities to form more covers. To avoid this situation, the compact operator is proposed to adjust the sensor order to increase the number of covers. This operator is applied to every offspring after mutation.
For an order-based chromosome, the compact operator checks the sensor groups successively. The redundant sensors ofeach cover are moved to the end of the chromosome such that they can later be collected again to form another cover. Restated, the compact operator rearranges the orders of redundant sensors to increase the number of covers. This operation
continues checking the newly formed covers until all redundant sensors have been moved out. For example, the left partof Fig. 4 displays an offspring after mutation. The compact operator checks the contribution of each sensor, which is{3, 0, 0, 1 j 2} for the offspring with a single cover C1 = {S3, S5, S4, S1}. Sensors S5 and S4 are made redundant from C1; however,they are probably helpful for forming another cover. The compact operator then moves sensors S5 and S4 to the end of theoffspring. As the right part of Fig. 4 shows, this operation helps the offspring to compact cover C1 into C01 = {S3, S1} and to forma new cover C02 = {S2, S5, S4}. The contribution of each sensor becomes {3, 1 j 2, 1, 1}, and the ﬁtness increases accordingly from
6 to 8. This example illustrates the fact that the compact operator can distribute the participation of sensors among covers
and can increase the number of covers.

5. Simulation results
A series of simulations was conducted to evaluate the performance of the proposed MA in extending WSN lifetime, incomparison with MCMCC [38], MCMIP [8], integer-coded GA (iGA) [23], and order-based GA. To assess the effect of the contribution ﬁtness function, two order-based GAs were considered: oGA1 and oGA2. The former adopts the number of covers asﬁtness whereas the latter employs the contribution value that is deﬁned in Section 4.2 as ﬁtness. Table 1 lists the operatorsand related parameters used in these algorithms. Notably, the mutation rate for oGA1, oGA2, and MA is the parameter for thenumber of swaps in the Poisson-distributed random generator.
The simulation instances of WSN are generated randomly; speciﬁcally, sensors and targets are deployed at random
over a 500  500 area. Each simulation setting includes 100 test instances and one run for each instance. The following subsections present and discuss the simulation results regarding the sensing range r, the number of targets jTj,
and the number of sensors jSj. Here, two factors qt and qs are deﬁned to characterize the test instances. Let T(s) be
the target set that is covered by sensor s, and let S(t) be the sensor set that covers target t. The two factors aredeﬁned by

1 XjTðsÞj;jSj s2S
1 X
qs ¼
jSðtÞj;jTj t2T

qt ¼

ð1Þ
ð2Þ

4824

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 1
Operators and parameters used in simulations.

Representation
Fitness
Population size
Parent selection
Crossover
Crossover rate
Mutation
Mutation rate
Local enhancement
Survivor selection
Termination

iGA

oGA1

oGA2

MA

Integer#Covers

Order#Covers

Order
Contribution

Order
Contribution

Uniform

Order

Bit-ﬂip
0.01
None

Swap
1.0
None

100
2-tournament selection
Order
1.0
Swap
1.0
None
(l + k)1000 generations

Order
Swap
1.0
Compact

where j  j denotes the cardinality. An upper bound on the number of covers K that is used in iGA [23] is determined as

ub ¼ min jSðtÞj:
t2T

ð3Þ

The value of ub gives the range of possible group numbers to which a target can be assigned, and thereby determines the
problem space of a SET K-COVER problem of extending WSN lifetime. Notably, for randomly generated test instances, qs
and ub are related: a large qs implies a large ub. The factor D is deﬁned as the difference between qs and ub:

D ¼ qs  ub:

ð4ÞThis measure represents the average number of sensors that should be excluded with respect to a single target when sensors
are partitioned to maximize the number of covers. A larger value of D implies that the algorithm should pay more attention
to picking out suitable sensors to maximize the number of covers.
Three measures are used for performance evaluation.
 Number of covers K: This number determines the maximum extension of WSN lifetime. The average and standard deviation are considered for the stochastic nature of test algorithms.
 Hit rate (HR): Since the maximum number, K, of covers in the test instances is unknown, the upper bound ub is used here
as a basis for evaluating solution quality. The hit rate is deﬁned as the percentage of runs that achieve ub covers:

HR ¼#runs that achieve ub covers
;
#runs

ð5Þ

where ub is decided by the smallest degree of target vertices in the bipartite graph of WSN.
 Running time: This time is measured on a simulation platform that uses C code on a Windows XP/Intel Core 2 Duo E6320
1.86 GHz machine.
5.1. Simulations with different sensing ranges
The purpose of the ﬁrst simulation was to investigate the performance of the proposed MA for different sensing ranges. As
Table 2 shows, extending the sensing range increases qt, qs, and ub. Notably, qs is related to ub for randomly generated test
instances. The simulation considers two sizes of WSN: the smaller WSN consists of 90 sensors and 10 targets, which size has
also been used in [8]; the larger WSN consists of 300 sensors and 500 targets, and was simulated to examine scalability.
Table 3 compares the solution quality of the six test algorithms. The implicit exhaustive search ensures that the MCMIP
always achieves the maximum number of covers; however, its exponential time complexity forbids experiments in which
sensing range exceeds 300 in the smaller WSN and all sensing ranges in the larger WSN. Table 4 further presents the resultsof a one-tailed paired t-test of the numbers of covers obtained using the test algorithms.
On the obtained number of covers, this study explored the effects of four elements in the proposed MA, namely evolutionary scheme, order-based representation, contribution ﬁtness, and local enhancement operator. First, the four EAs, viziGA, oGA1, oGA2, and MA, outperformed MCMCC in terms of the number of covers obtained, except for iGA with r P 300
in both WSNs and oGA1 with r 6 400 in the larger WSN. This superior performance of EAs over MCMCC shows the effectiveness of the evolutionary scheme in maximizing the number of covers. Second, the performance of iGA degrades as the sensing range r increases and is even worse than that of MCMCC for r P 300. This weakness of iGA is caused by the use of ub toindicate the range of potential values of genes, even though it may not equal the maximum number K, especially in large qs
WSNs. The error in estimating K incurs trivial representation space in iGA and a subsequent inefﬁcient search for the optimal
solution. The order-based representation used in oGA1, oGA2, and MA, nevertheless, overcomes this weakness by removing
the need for ub, which is beneﬁcial for large sensing ranges. Third, the number of covers achieved by oGA2 is larger than or atleast comparable to that achieved by oGA1. This outcome conﬁrms that the contribution ﬁtness improves the performance of4825

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 2Average (Avg.) and standard deviation (S.D.) of qt, qs, ub, and D over 100 problem instances for different sensing ranges r with jSj sensors and jTj targets.
jSj

qt

r

jTj

qs

Avg.

ub

D

S.D.

Avg.

S.D.

Avg.

S.D.

Avg.

90

10

100
150
200
250
300
350
400
450
500

1.04
2.15
3.44
4.79
6.12
7.35
8.43
9.26
9.74

0.14
0.26
0.32
0.44
0.54
0.48
0.37
0.24
0.12

9.32
19.35
30.94
43.07
55.09
66.16
75.89
83.31
87.64

1.26
2.36
2.90
3.98
4.85
4.32
3.30
2.19
1.07

4.13
9.84
16.77
25.18
34.78
45.54
58.31
70.37
80.53

1.61
2.64
4.47
4.82
6.13
6.84
6.55
5.98
4.20

5.19
9.51
14.17
17.89
20.31
20.62
17.58
12.94
7.11

300

500

100
150
200
250
300
350
400
450
500

52.52
107.55172.69241.01309.15371.62425.36464.60487.67

0.93
2.20
3.75
4.72
5.34
5.18
4.34
2.82
1.20

31.51
64.53
103.61144.61
185.49222.97255.22278.76292.60

0.56
1.32
2.25
2.83
3.20
3.11
2.60
1.69
0.72

8.69
20.20
36.01
58.16
84.71
115.57151.43193.62238.08

2.17
3.35
4.38
5.04
5.81
6.85
6.73
6.38
6.24

22.82
44.33
67.60
86.45
100.78107.40103.7985.14
54.52

Table 3
Average (Avg.), standard deviation (S.D.), and hit rate (HR) of the number of covers obtained for different sensing ranges (r) with jSj sensors and jTj targets.
Boldface denotes the best result among the six test algorithms.
jSj

90

300

jTj

10

500

r

ub

MCMIP

MCMCC

Avg. (S.D.)

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

4.13
(1.61)
9.78(2.58)
16.41(4.15)
24.55(4.43)
33.97(5.62)
44.67(6.16)
56.70(5.88)
69.12(5.82)
80.03(4.27)

1.00

4.13(1.61)
9.84(2.64)
16.77(4.47)
25.18(4.82)
34.75(6.09)
45.12(6.33)
56.64(5.74)
68.54(6.12)
79.75(4.55)

1.00

4.12(1.60)
9.79(2.54)
16.67(4.34)
25.15(4.79)
34.64(5.99)
45.20(6.40)
57.26(5.89)
69.37(5.80)
80.06(4.27)

0.99

4.13(1.61)
9.84(2.64)
16.77(4.47)
25.18(4.82)
34.75(6.09)
45.27(6.48)
57.29(5.87)
69.36(5.81)
80.06(4.27)

1.00

4.13(1.61)
9.84(2.64)
16.77(4.47)
25.18(4.82)
34.76(6.10)
45.28(6.49)
57.39(5.89)
69.39(5.81)
80.06(4.27)

1.00

8.28(1.93)
19.64(3.01)
35.59(4.15)
56.46(4.42)
80.55(4.01)
110.34(4.40)
142.51(4.09)
174.71(4.41)
207.86(5.29)

0.67

8.67(2.13)
20.16(3.31)
35.96(4.29)
57.87(4.76)
83.26(4.75)
112.44(4.74)
144.75(4.53)
176.58(4.11)
208.98(5.35)

0.98

8.69(2.17)
20.20(3.35)
36.00(4.36)
58.15(5.03)
84.59(5.66)
114.92(6.02)
148.74(4.99)
178.66(4.00)
209.20(5.28)

1.00

100

4.13

150

9.84

200

16.77

250

25.18

300

34.78

4.13
(1.61)
9.84(2.64)
16.77(4.47)
25.18(4.82)
–

350

45.54

–

400

58.31

–

450

70.37

–

500

80.53

–

100

8.69

–

150

20.20

–

200

36.01

–

250

58.16

–

300

84.71

–

350

115.57–400

151.43–450

193.62–500

238.08

–

iGA

0.95
0.75
0.66
0.61
0.64
0.47
0.55
0.73

0.71
0.76
0.37
0.24
0.23
0.07
0.00
0.00

8.65
(2.11)
20.07(3.19)
35.87(4.21)
57.46(4.32)
78.85(4.04)
100.07(5.57)
125.18(7.02)
149.43(8.04)
179.30(8.73)

oGA1

1.00
1.00
1.00
0.97
0.89
0.66
0.66
0.75
0.97
0.94
0.92
0.73
0.32
0.04
0.01
0.00
0.00

7.43
(1.08)
18.43(1.98)
34.32(3.20)
55.90(3.59)
80.37(3.68)
109.50(4.07)
142.75(4.37)
175.76(4.13)
208.93(5.26)

oGA2

0.95
0.92
0.91
0.89
0.85
0.62
0.64
0.76
0.40
0.37
0.34
0.28
0.13
0.05
0.02
0.00
0.00

MA

1.00
1.00
1.00
0.98
0.88
0.62
0.64
0.76

0.96
0.96
0.78
0.42
0.24
0.06
0.00
0.00

1.00
1.00
1.00
0.98
0.87
0.67
0.66
0.76

1.00
0.99
0.99
0.89
0.69
0.26
0.01
0.00

order-based GA. Finally, the compact operator enables the MA to improve signiﬁcantly oGA2 in terms of the number of covers and to yield the same number of covers as obtained using MCMIP. This demonstrates that the MA is highly capable of4826

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 4
Results of one-tailed paired t-test of the numbers of covers obtained from X and Y algorithms (denoted by X vs. Y) for different sensing ranges r with jSj sensors
and jTj targets. Positive p-values indicate that X is superior to Y, and vice versa. Boldface denotes that X is signiﬁcantly better than Y. N/A indicates that X and Y
yield identical results in all test instances.
oGA1 vs.
MCMCC

oGA1 vs.
iGA

oGA2 vs.
MCMCC

oGA2 vs.
iGA

oGA2 vs.
oGA1

MA vs.
MCMCC

MA vs.
iGA

100 100 N/A
150 1.66E02
200 3.00E07
250 2.40E07
300 7.20E10
350 8.29E05
400 3.73E01450 5.28E04
500 9.46E04

1.60E01
3.70E01
1.61E05
1.51E07
8.84E09
9.93E08
1.17E07
1.68E05
4.16E02

1.60E01 N/A
1.23E02 1.66E02
3.45E03 3.00E07
4.16E02 2.40E07
3.50E03 1.41E09
9.79E02 5.09E08
8.14E05 7.93E08
6.35E07 1.70E05
2.49E04 4.16E02

N/A
N/A
N/A
N/A
5.00E01
1.07E02
2.89E05
8.47E07
2.49E04

1.60E01
1.23E02
3.45E03
4.16E02
3.50E03
3.52E02
2.35E01
2.83E01
N/A

N/A
1.66E02
3.00E07
2.40E07
7.15E10
1.15E08
8.96E09
5.63E06
4.16E02

N/A
1.60E01
N/A
1.23E02
N/A
3.45E03
N/A
4.16E02
1.60E01 1.15E03
1.29E02 5.35E03
2.30E06 3.00E04
2.95E07 7.92E02
2.49E04 N/A

N/A
N/A
N/A
N/A
2.83E01
3.28E01
1.71E03
4.16E02
N/A

300 500 100 9.87E08
150 3.09E05
200 1.53E03
250 2.33E07
300 3.96E04
350 7.16E25
400 5.53E43
450 1.45E63
500 2.44E74

7.25E12
4.33E11
1.21E11
2.28E03
2.49E01
2.12E03
1.87E01
1.48E07
6.84E18

3.50E15 8.15E09
2.71E15 8.22E07
7.52E16 4.18E06
3.80E16 2.63E12
8.53E04 1.68E14
4.67E23 1.04E09
1.01E41 1.63E12
1.04E62 1.54E19
3.23E74 1.19E19

2.08E01
7.52E02
4.16E02
9.14E04
6.92E13
3.82E27
4.90E44
1.06E64
2.34E75

1.90E15
1.51E15
1.09E15
5.63E20
3.59E24
3.45E23
1.47E13
9.89E08
2.39E01

4.52E09
4.35E07
1.17E06
1.24E14
5.76E19
5.69E19
3.87E35
2.64E44
3.32E26

5.14E02 4.69E15
2.09E02 2.25E15
5.81E03 1.94E15
2.77E05 1.47E19
3.75E14 3.06E27
5.42E28 6.03E32
3.19E46 8.13E42
4.43E69 3.65E38
5.46E76 1.66E06

7.92E02
2.25E02
5.14E02
1.39E05
3.17E13
2.25E21
9.82E32
3.44E32
3.32E06

jSj

jTj

90

r

iGA vs.
MCMCC

MA vs.
oGA1

MA vs.
oGA2

achieving global optimal solutions. The MA substantially outperforms all other test algorithms except MCMIP in terms of thenumber of covers obtained. The advantage of oGA2 and MA over the other test algorithms increases with the WSN size.
In terms of hit rate, the comparative results somewhat differ between the smaller and larger WSNs. In the smaller WSN,
the MA, iGA, and oGA2 perform best, followed by oGA1 with only a slightly poorer performance; MCMCC yields relatively
low hit rates, especially for 200 6 r 6 450. Fig. 5, which plots the variation of hit rate against sensing range, indicates that
MA and iGA yield similar hit rates, while MCMCC has a low hit rate for most of the test sensing ranges. Notably, the low
hit rates for r P 400 do not imply poor performance of the test algorithms. Rather, they reﬂect the signiﬁcant difference
between the optimal number K and the upper bound ub. Hence, given the deﬁnition of hit rate, the algorithm cannot havea high hit rate, even though it can achieve the maximum number of covers. In the larger WSN, the compact operator in the
MA is very effective in increasing the hit rate, which fact is reﬂected by the apparent discrepancy between the HR of the MA
and those of all other test algorithms. Moreover, oGA2 outperforms oGA1 and iGA. This outcome veriﬁes the utility of thecontribution ﬁtness in increasing the number of covers obtained. The oGA1 performs poorly in the larger WSN, revealing
the need for order-based representation to improve the ﬁtness function or perform local enhancement, as in the proposed
MA.
Table 5 lists the running time of the six test algorithms for different sensing ranges. For all test algorithms, the running
time generally increases with sensing range. Owing to its implicit exhaustive search, MCMIP requires much longer running
time than the other algorithms. MCMCC has the shortest running time. The EAs require somewhat more time than MCMCC,
but much less time than MCMIP. The difference between the running time of oGA1 and that of oGA2 reﬂects the effect of theﬁtness function. At small sensing ranges (r 6 200), oGA2 achieves shorter running time by using contribution ﬁtness, andyet, as r P 250, the contribution ﬁtness of oGA2 results in longer running time than oGA1. Concerning the cost of local

MCMCC
iGA
oGA1
oGA2
MA

100
90

MCMCC
iGA
oGA1
oGA2
MA

100
80
60

HR

HR

80
70

40

60

20

50
100

0
150

200

250
300
350
Sensing Range

400

450

500

100

150

200

250
300
350
Sensing Range

400

450

500

Fig. 5. Hit rates of MCMCC, iGA, oGA1, oGA2, and MA for different sensing ranges (r) with jSj = 90 and jTj = 10 (left) and with jSj = 300 and jTj = 500 (right).

4827

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833
Table 5
Running time of MCMIP, MCMCC, iGA, oGA1, oGA2, and MA for different sensing ranges (r) with jSj sensors and jTj targets.
r

100
150
200
250
300
350
400
450
500

jSj = 90, jTj = 10

jSj = 300, jTj = 500

MCMIP

MCMCC

iGA

oGA1

oGA2

MA

MCMCC

iGA

oGA1

oGA2

MA

0.33
13.99
208.171174.10
–
–
–
–
–

0.00
0.00
0.01
0.02
0.03
0.05
0.05
0.05
0.06

2.13
3.47
4.49
2.39
6.40
7.09
8.08
8.66
9.96

1.69
1.87
2.01
2.13
2.17
2.21
2.23
2.23
2.25

1.47
1.74
1.94
2.11
2.25
2.45
2.60
2.73
2.86

2.16
2.46
2.54
2.57
2.53
2.63
2.75
2.88
3.02

2.20
8.09
16.20
41.45
68.35
89.33
103.52115.62112.03

32.08
58.46
90.23
126.35164.74203.39242.26305.61374.68158.99166.48185.26202.33210.35213.84212.21209.08212.70115.51165.66212.93250.21
269.64280.41281.68281.97295.91

170.39225.80236.75262.00296.61284.79291.35293.52300.45enhancement, i.e., the compact operator, the MA requires more running time than oGA2 does. However, the increase in running time associated with compact operation gradually declines as the sensing range increases. The iGA has longer running
time than MCMCC, order-based GAs, and the MA. Increasing the sensing range has a strongly negative effect on iGA running
time since its search space depends on ub, which increases with the sensing range r.
5.2. Simulations with different numbers of targets
The second simulation tested the performance of the MA on WSNs with different numbers of targets. This simulation considered two settings for the number of sensors and sensing range of each. The ﬁrst involved a WSN comprising 90 sensors
with r = 250, which was used in [8]. The second involved jSj = 300 sensors with a sensing range of r = 400 to check the scalability of the test algorithms. Table 6 lists the characteristics of these problem instances for different numbers of targets, anddemonstrates that adding targets in the WSN does not affect qs, but does reduce ub and increase qt and D. Increasing thesensing range from 250 to 400 also increases qs. The effects of these changes are discussed below.
Table 7 compares the number of covers and hit rate obtained for different numbers of targets. The table shows only a few
results for MCMIP because, as indicated by Table 9, its high cost limits the number of targets in the experiments. For thesmaller sensing range (r = 250), the results in Table 7 demonstrate that iGA, oGA2, and MA perform very well for all tested
numbers of targets. Notably, MA can achieve a number of covers that equals the upper bound ub. The t-test results in Table 8
reveal no signiﬁcant variation among the results obtained using iGA, oGA2, and MA. Additionally, oGA1 generates signiﬁcantly fewer covers than the above three algorithms. The difference between the simulation results for oGA1 and oGA2,
moreover, validates the advantage of using contribution ﬁtness. The four EAs (iGA, oGA1, oGA2, and MA) all outperform

Table 6
Average (Avg.) and standard deviation (S.D.) of qt, qs, ub, and D over 100 problem instances for different numbers jTj of targets to be covered by jSj sensors withsensing range r.
jSj

r

jTj

qt

qs

ub

D

Avg.

S.D.

Avg.

S.D.

Avg.

S.D.

Avg.

90

250

10
20
30
40
50
75
100
150
200
250
500

4.79
9.66
14.52
19.33
24.12
36.17
48.35
72.42
97.11
120.79241.52

0.44
0.66
0.87
1.05
1.19
1.74
2.06
2.57
3.30
4.14
7.94

43.07
43.49
43.56
43.50
43.41
43.40
43.52
43.45
43.70
43.49
43.47

3.98
2.96
2.60
2.36
2.15
2.09
1.86
1.54
1.48
1.49
1.43

25.18
21.31
21.13
19.59
19.41
18.58
17.85
17.26
16.55
16.20
15.54

4.82
3.77
3.91
3.71
3.10
2.95
2.83
2.67
2.61
2.38
2.26

17.89
22.18
22.43
23.91
24.00
24.82
25.67
26.19
27.15
27.29
27.93

300

400

10
20
30
40
50
75
100
150
200
250
500

8.45
16.98
25.59
34.05
42.51
63.74
84.73
127.71
170.14212.60425.36

0.38
0.57
0.73
0.74
0.94
1.19
1.32
1.88
2.25
2.47
4.34

253.45254.66255.88255.38255.09254.94254.20255.41
255.21
255.12
255.22

11.38
8.48
7.34
5.55
5.62
4.76
3.97
3.76
3.38
2.97
2.60

193.67181.94178.43173.02167.79167.39162.87159.84157.96155.91151.43

21.10
17.13
17.01
15.13
13.82
10.90
9.58
8.00
9.09
6.92
6.73

59.78
72.72
77.45
82.36
87.30
87.55
91.33
95.57
97.25
99.21
103.79

4828

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 7
Average (Avg.), standard deviation (S.D.), and hit rate (HR) of the number of covers obtained for different numbers of targets (jTj) with jSj sensors and sensing
range r. Boldface denotes the best result among the six test algorithms.
jSj

90

300

r

250

400

jTj

ub

MCMIP

MCMCC

Avg. (S.D.)

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

24.55
(4.43)
20.80(3.45)
20.50(3.39)
18.98(3.22)
18.84(2.68)
18.04(2.56)
17.40(2.44)
16.73(2.32)
16.03(2.35)
15.82(2.24)
15.17(2.15)

0.66

25.18(4.82)
21.30(3.76)
21.04(3.73)
19.58(3.69)
19.40(3.09)
18.52(2.87)
17.78(2.71)
17.23(2.64)
16.52(2.56)
16.20(2.38)
15.51(2.24)

1.00

25.15(4.79)
21.23(3.69)
20.87(3.59)
19.45(3.56)
19.29(2.94)
18.40(2.73)
17.67(2.59)
17.05(2.46)
16.33(2.37)
16.11(2.28)
15.42(2.15)

0.91

25.18(4.82)
21.31(3.77)
21.09(3.85)
19.58(3.69)
19.41(3.10)
18.57(2.93)
17.85(2.83)
17.26(2.67)
16.54(2.60)
16.20(2.38)
15.54(2.26)

1.00

25.18(4.82)
21.31(3.77)
21.13(3.91)
19.59(3.71)
19.41(3.10)
18.58(2.95)
17.85(2.83)
17.26(2.67)
16.55(2.61)
16.20(2.38)
15.54(2.26)

1.00

10

25.18

20

21.31

30

21.13

40

19.59

25.18
(4.82)
21.31(3.77)
21.13(3.91)
–

50

19.41

–

75

18.58

–

100

17.85

–

150

17.26

–

200

16.55

–

250

16.20

–

500

15.54

–

10

193.67–20

181.94–30

178.43–40

173.02–50

167.79–75

167.39–100

162.87–150

159.84–200

157.96–250

155.91–500

151.43–

189.23(19.39)176.72(13.93)171.56(13.27)165.69(11.81)160.78(10.19)158.77(7.91)
154.59(7.36)
150.54(5.78)
148.98(6.04)
147.01(4.93)
142.51(4.09)

iGA

0.72
0.63
0.66
0.66
0.65
0.69
0.65
0.67
0.71
0.71
0.44
0.41
0.26
0.21
0.22
0.11
0.11
0.12
0.09
0.10
0.07

188.16(18.81)173.40(13.02)167.25(11.46)160.38(10.12)154.94(8.01)
148.73(9.35)
144.30(8.17)
137.20(8.40)
133.93(6.67)
131.10(7.45)
125.18(7.02)

oGA1

0.99
0.95
0.99
0.99
0.96
0.95
0.97
0.99
1.00
0.97
0.56
0.43
0.26
0.11
0.15
0.09
0.03
0.04
0.02
0.01
0.01

189.76(18.98)176.62(13.71)
171.79(12.98)166.08(11.70)160.98(10.29)158.71(7.72)
154.83(7.19)
151.05(5.39)
148.65(6.15)
147.01(4.73)
142.75(4.37)

oGA2

0.95
0.82
0.87
0.90
0.88
0.87
0.81
0.82
0.91
0.89
0.46
0.38
0.20
0.18
0.13
0.07
0.03
0.05
0.02
0.02
0.02

189.93(19.07)177.15(13.88)172.38(13.03)167.07(11.79)162.09(10.33)160.08(7.63)
156.19(7.08)
152.45(5.79)
150.55(6.19)
148.42(4.76)
144.75(4.53)

MA

1.00
0.96
0.99
1.00
0.99
1.00
1.00
0.99
1.00
1.00
0.43
0.49
0.24
0.20
0.18
0.10
0.08
0.08
0.09
0.03
0.06

190.93(19.34)178.54(13.99)174.49(13.26)169.47(12.04)164.55(10.72)163.35(8.20)
159.78(7.42)
156.46(6.38)
154.39(6.76)
152.80(5.15)
148.74(4.99)

1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.59
0.55
0.47
0.38
0.37
0.29
0.35
0.18
0.25
0.24
0.26

MCMCC in terms of the number of covers obtained and the hit rate. This superiority of EAs reconﬁrms the beneﬁt of the evolutionary scheme in extending WSN lifetime with small sensing ranges.
As the sensing range r increases to 400, the hit rate of the test algorithms apparently decreases, and this decline is further
intensiﬁed by the increase of targets. In the problem instances considered herein, the reduction in the hit rate corresponds tothe increase in D, implying that more sensors should be excluded when sensors are arranged to cover a certain target. In
addition, overestimating the maximum number K using ub still impairs the performance of iGA. The order-based EAs, including oGA1, oGA2, and MA, resolve this issue by eliminating the need for an upper bound on or an assumption about the maximum number of covers. Further, the proposed MA can achieve signiﬁcantly more covers than the other test algorithms can,and this signiﬁcance increases with the number of targets. Fig. 6 further shows that the MA achieves the highest hit rates for
all tested numbers of targets. These experimental results demonstrate the excellent performance of the proposed MA in generating covers for extending the WSN lifetime.
Table 9 compares the running time of the six test algorithms in this simulation. The required running time of all test algorithms increases with the number of targets. The MCMCC is the fastest of all the test algorithms; however, its unsatisfactory
solution quality detracts greatly from its efﬁciency. The comparison of test EAs indicates that iGA requires less running timethan oGA1, oGA2, and MA for problem instances with a small sensing range (r = 250). Conversely, for problem instances with
r = 400, iGA has longer running time than oGA1, oGA2, and even the MA, for all numbers of targets except jTj = 500. This

4829

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 8Results of one-tailed paired t-test of the numbers of covers obtained from X and Y algorithms (denoted by X vs. Y) for different numbers jTj of targets with jSj
sensors and sensing range r. Positive p-values indicate that X is superior to Y, and vice versa. Boldface denotes that X is signiﬁcantly better than Y. N/A indicatesthat X and Y have identical results in all test instances.
jSj

r

jTj

iGA vs.
MCMCC

oGA1 vs.
MCMCC

oGA1 vs.
iGA

oGA2 vs.
MCMCC

oGA2 vs.
iGA

oGA2 vs.
oGA1

MA vs.
MCMCC

MA vs.
iGA

MA vs.
oGA1

MA vs.
oGA2

90

250

10
20
30
40
50
75
100
150
200
250
500

2.40E07
6.40E07
1.83E09
2.42E08
5.49E08
2.27E08
1.60E07
1.32E07
1.97E08
2.60E07
1.80E07

1.51E07
1.48E06
1.52E06
1.65E07
2.29E07
2.51E06
1.51E05
2.30E05
3.15E05
8.60E05
4.19E05

4.16E02
2.59E02
1.79E03
1.06E04
3.50E03
3.33E03
3.52E04
3.72E05
8.49E05
1.15E03
5.91E03

2.40E07
6.57E07
2.63E09
2.42E08
9.55E08
7.30E09
5.09E08
2.16E08
3.05E08
2.60E07
2.89E08

N/A
1.60E01
1.39E01
N/A
1.60E01
2.92E02
1.71E02
4.16E02
2.65E01
N/A
4.16E02

4.16E02
1.59E02
5.03E05
1.06E04
2.08E03
4.20E04
3.96E04
6.14E06
1.39E05
1.15E03
5.38E04

2.40E07
6.57E07
2.37E09
4.11E08
9.55E08
6.23E09
5.09E08
2.16E08
3.60E08
2.60E07
2.89E08

N/A
1.60E01
4.74E02
1.60E01
1.60E01
2.87E02
1.71E02
4.16E02
1.60E01
N/A
4.16E02

4.16E02
1.59E02
3.80E05
1.67E04
2.08E03
5.92E04
3.96E04
6.14E06
1.57E05
1.15E03
5.38E04

N/A
N/A
2.25E02
1.60E01
N/A
1.60E01
N/A
N/A
1.60E01
N/A
N/A

300

400

10
20
30
40
50
75
100
150
200
250
500

1.48E02
8.46E08
1.71E08
4.71E12
2.75E13
2.12E20
4.95E25
6.59E32
6.72E36
1.32E35
5.53E43

1.10E02
2.50E01
1.29E01
4.90E02
2.32E01
4.05E01
1.37E01
2.56E02
9.52E02
5.00E01
1.87E01

1.36E04
1.56E07
2.97E09
9.93E14
5.32E14
3.81E20
1.51E23
1.13E31
8.80E34
1.77E34
1.01E41

2.34E03
5.35E03
4.19E04
8.96E09
5.29E07
5.88E06
2.79E10
1.09E09
2.83E10
8.59E07
1.63E12

4.57E05
1.03E08
4.14E11
1.07E15
4.00E17
1.85E22
7.08E27
1.21E33
1.11E38
2.21E37
4.90E44

9.49E02
1.85E05
2.63E04
1.20E07
2.36E09
3.13E09
1.80E10
1.12E09
2.00E14
4.09E10
1.47E13

8.12E10
1.98E13
2.39E17
3.91E20
4.37E20
1.23E28
7.78E31
6.09E31
5.82E33
2.22E32
3.87E35

3.30E08
2.90E12
7.90E16
6.85E21
3.65E21
3.21E27
7.94E32
9.90E36
2.36E41
4.18E41
3.19E46

1.76E11
3.92E16
4.04E21
5.47E23
3.50E26
1.43E34
5.27E40
6.83E38
5.89E40
2.59E41
8.13E42

6.50E13
1.50E13
7.38E19
1.03E21
3.96E22
1.25E28
1.22E29
3.72E28
4.95E30
7.30E32
9.82E32

outcome reveals that overestimation of K by upper bound in iGA degrades not only solution quality but also running time.
The results in Table 9 also demonstrate that using contribution ﬁtness or the compact operator increases running time. However, the merits of these two elements, i.e., higher number of covers obtained and higher hit rate, still outweigh their slightly
increased cost in running time.

5.3. Simulations with different numbers of sensors
The third simulation compared the performance of the MA across different numbers of sensors. This simulation used two
WSN settings: one with ten targets and a sensing range of 250 and the other with 500 targets and a sensing range of 400.
Similarly, the former was used in [8] and the latter was applied to examine scalability. Table 10 demonstrates, although qt isunchanged, qs, ub, and D increase with the number of sensors jSj. Extending the sensing range from 250 to 400 further increases qs. Increasing the number of targets from 10 to 500 considerably augments qt.
Table 11 shows that the EAs outperform MCMCC in terms of the obtained number of covers in all except the two cases of
jSj P 200 with jTj = 500 and r = 400, in which iGA is inferior to MCMCC. These simulation results verify not only theeffectiveness of the evolutionary scheme but also the advantage of the order-based representation over the integer

100

MCMCC
iGA
oGA1
oGA2
MA

60

95
50

90

40
HR

HR

85
80
75

20
MCMCC
iGA
oGA1
oGA2
MA

70
65
60

30

50

100

150

200

250 300#Targets

350

400

10

450

500

0

50

100

150

200

250 300#Targets

350

400

450

500

Fig. 6. Hit rates of MCMCC, iGA, oGA1, oGA2, and MA for different numbers of targets (jTj) with jSj = 90 and r = 250 (left) and with jSj = 300 and r = 400(right).

4830

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 9Running time of MCMIP, MCMCC, iGA, oGA1, oGA2, and MA for different numbers of targets (jTj) with jSj sensors and sensing range r.
jSj = 90, r = 250

jTj

10
20
30
40
50
75
100
150
200
250
500

jSj = 300, r = 400

MCMIP

MCMCC

iGA

oGA1

oGA2

MA

MCMCC

iGA

oGA1

oGA2

MA

1234.63
1729.11
18024.71

0.02
0.05
0.08
0.11
0.14
0.20
0.27
0.42
0.51
0.63
1.24

2.39
2.65
3.01
3.30
3.64
9.25
11.24
14.96
17.03
20.65
36.60

2.13
3.36
4.60
5.75
7.01
9.94
12.80
18.61
24.05
34.93
63.20

2.11
3.43
4.87
6.22
7.73
11.46
15.17
22.62
29.84
37.31
76.96

2.54
4.05
5.55
7.26
8.72
12.69
16.79
25.90
33.86
41.60
84.77

1.85
4.10
6.35
8.27
10.45
15.59
20.42
31.51
41.05
52.47
103.52

53.41
62.54
69.43
74.28
77.61
87.46
100.92134.72143.55149.51
242.26

7.04
11.55
16.45
20.20
24.44
35.36
46.00
66.82
87.92
110.67212.21

8.44
14.18
19.96
25.58
30.89
45.44
58.95
86.39
114.26141.98281.68

8.82
14.47
20.23
25.95
31.56
46.09
60.27
89.19
117.67144.75291.35

Table 10
Average (Avg.) and standard deviation (S.D.) of qt, qs, ub, and D over 100 problem instances for different numbers jSj of sensors with sensing range r to cover jTj
targets.
r

jTj

qt

jSj

qs

Avg.

ub

D

S.D.

Avg.

S.D.

Avg.

S.D.

Avg.

10

250

90
100
200
300

4.79
4.86
4.84
4.86

0.44
0.46
0.47
0.42

43.07
48.56
96.76
145.83

3.98
4.57
9.41
12.73

25.18
28.76
57.98
88.92

4.82
6.75
11.89
14.86

17.89
19.80
38.78
56.91

500

400

90
100
200
300

426.24426.13424.34425.36

6.81
6.73
5.34
4.34

76.72
85.23
169.74255.22

1.23
1.35
2.14
2.60

43.88
48.63
101.08151.43

3.49
3.47
5.50
6.73

32.84
36.60
68.66
103.79

Table 11
Average (Avg.), standard deviation (S.D.), and hit rate (HR) of the number of covers obtained for different numbers of sensors (jSj) with jTj targets and sensing
range r. Boldface denotes the best result among the six test algorithms.
jTj

10

500

r

250

400

jSj

ub

MCMIP

MCMCC

Avg. (S.D.)

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

Avg. (S.D.)

HR

24.55
(4.43)
27.94(6.03)
55.86(9.98)
85.78(13.10)

0.66

25.18
(4.82)
28.73(6.69)
57.87(11.73)88.34(14.19)

1.00

25.15
(4.79)
28.57(6.56)
57.27(11.14)87.57(13.57)

0.91

25.18
(4.82)
28.75(6.74)
57.78(11.64)88.29(14.12)

1.00

25.18
(4.82)
28.76(6.75)
57.97(11.88)88.85(14.74)

1.00

42.11
(2.47)
46.87(2.61)
95.18(3.98)
142.51(4.09)

0.33

42.94(2.68)
47.63(2.80)
89.32(4.81)
125.18(7.02)

0.64

42.68(2.64)
47.31(2.68)
95.81(3.88)
142.75(4.37)

0.41

43.13(2.87)
47.92(2.89)
97.40(3.77)
144.75(4.53)

0.63

90

25.18

100

28.76

200

57.98

25.18
(6.01)
28.76(6.75)
–

300

88.92

–

90

43.88

–

100

48.63

–

200

101.08–300

151.43

–

iGA

0.66
0.57
0.47

0.35
0.07
0.07

oGA1

0.97
0.93
0.85

0.61
0.05
0.01

oGA2

0.88
0.73
0.64

0.38
0.06
0.02

MA

0.99
0.89
0.78

0.59
0.17
0.06

43.57
(3.17)
48.28(3.15)
99.57(4.35)
148.74(4.99)

1.00
0.99
0.96
0.80
0.77
0.43
0.26

representation. The statistical test results in Table 12 further indicate that the superiority of oGA2 and MA over oGA1 andoGA2 grows with the number of sensors. As the number of sensors in WSN increases, the effects of the contribution ﬁtness
adopted in oGA2 and the compact operator employed in MA become more signiﬁcant.
Fig. 7 displays how hit rate varies with the number of sensors for all test algorithms except MCMIP. The hit rate declined
as more sensors were added to WSNs. As mentioned above, this reduced hit rate does not necessarily imply a deteriorated
algorithmic performance, but it does reﬂect the discrepancy between ub and the maximal number of covers K. The ﬁgure
consistently demonstrates that MA > oGA2 > MCMCC. Similar to the results for the number of covers, iGA had high hit rates
for jTj = 10 with r = 250 but very low hit rates for jTj = 500 with r = 400. However, MCMCC outperformed oGA1 and iGA for
jSj P 200 in the latter case.

4831

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

Table 12Results of one-tailed paired t-test of the numbers of covers obtained from X and Y algorithms (denoted by X vs. Y) for different numbers jSj of sensors with jTj
targets and sensing range r. Positive p-values indicate that X is superior to Y, and vice versa. Boldface denotes that X is signiﬁcantly better than Y. N/A indicatesthat X and Y have identical results in all test instances.
jTj

r

jSj

iGA vs.
MCMCC

oGA1 vs.
MCMCC

oGA1 vs.
iGA

oGA2 vs.
MCMCC

oGA2 vs.
iGA

oGA2 vs.
oGA1

MA vs.
MCMCC

MA vs.
iGA

MA vs.
oGA1

MA vs.
oGA2

10

250

90
100
200
300

2.40E07
1.08E08
6.06E09
2.10E10

1.51E07
6.44E08
2.84E08
1.87E08

4.16E02
1.52E03
1.82E06
1.67E06

2.40E07
1.50E08
4.82E09
4.21E10

N/A
1.60E01
6.44E02
2.97E01

4.16E02
5.92E04
7.97E06
2.64E07

2.40E07
1.86E08
8.67E09
1.81E10

N/A
4.16E02
5.84E03
2.14E03

4.16E02
3.65E04
3.44E06
1.24E07

N/A
1.60E01
3.58E03
1.16E04

500

400

90
100
200
300

1.36E10
1.54E08
8.16E20
5.53E43

5.82E08
3.37E05
1.90E03
1.87E01

3.66E03
1.52E03
2.44E20
1.01E41

3.20E15
4.35E16
7.32E21
1.63E12

1.82E02
2.67E03
1.73E27
4.90E44

2.29E07
8.89E10
5.14E16
1.47E13

6.42E19
1.74E18
8.54E35
8.93E36

1.30E07
1.72E08
7.61E30
9.58E47

1.89E16
9.33E17
5.84E35
1.18E41

5.18E07
4.89E07
6.28E24
9.82E32

MCMCC
iGA
oGA1
oGA2
MA

80

100

70
90

60
50
HR

HR

80
70

40
30

60 MCMCC
iGA
oGA1
oGA2
50
MA

20
10

100

150

200
#Sensors

250

0

300

100

150

200
#Sensors

250

300

Fig. 7. Hit rates of MCMCC, iGA, oGA1, oGA2, and MA for different numbers of sensors j(S)j with jTj = 10 and jrj = 250 (left) and with jTj = 500 and jrj = 400(right).

Table 13
Running time of MCMIP, MCMCC, iGA, oGA1, oGA2, and MA for different numbers of sensors (jSj) with jTj targets and sensing range r.
jSj

jTj = 10, r = 250

jTj = 500, r = 400

MCMIP

MCMCC

iGA

oGA1

oGA2

MA

MCMCC

iGA

oGA1

oGA2

MA

90
100
200
300

1234.634719.81
–
–

0.02
0.03
0.24
0.76

2.39
2.71
6.43
11.52

2.13
2.33
4.58
6.78

2.11
2.32
4.55
6.75

2.57
2.84
5.37
7.78

3.01
4.31
34.89
103.52

71.72
86.18
198.26242.2671.17
71.08
142.06212.21

90.31
93.16
188.29281.6892.39
98.65
190.42291.35

Table 13 indicates that running time generally increased with the number of sensors. Additionally, oGA1 was faster thaniGA, conﬁrming the advantage of order-based representation in terms of running time. A comparison with oGA1 reveals thatthe contribution ﬁtness of oGA2 did not inﬂuence the running time for jTj = 10 with r = 250, but it increased the running timefor jTj = 500 with r = 400. The use of the compact operator slightly increased running time, which is the cost of the excellent
performance of MA in solution quality.
6. Conclusions
This study proposes an MA for extending WSN lifetime, formulated as the SET K-COVER problem. Speciﬁcally, the proposed MA follows the evolutionary scheme of GA. By viewing sensor arrangement as a process of collecting covers rather
than one of partitioning, chromosomes in the MA are represented as collecting orders. This study presents a novel ﬁtness
function based on the contribution of each sensor to forming a cover. Furthermore, the compact operator is devised for local
enhancement of the MA.
The proposed MA has the following advantages.

4832

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

1. The evolutionary scheme of GA contributes to global search.
2. The order-based representation eliminates the need for, and therefore the sensitivity to, the upper bound on or assumptions about the maximum number of covers.
3. The contribution ﬁtness enhances the differentiation of promising chromosomes.
4. The compact operator enhances the group composition to increase the number of covers.
To evaluate the proposed algorithm, this study conducted comprehensive simulations regarding sensing range, number oftargets, and number of sensors in WSNs. The simulation results conﬁrm the above-stated advantages of the MA in terms of
the obtained number of covers, hit rate, and running time. In all of the problem instances, the proposed MA outperformed
one heuristic and three other EAs in terms of the number of covers obtained and the hit rate. Notably, it achieved the same
number of covers with much shorter running time than an exact algorithm requires. The scalability of the MA superiority
was veriﬁed through simulations with different sensing ranges and numbers of sensors and targets. These preferable outcomes validate the effectiveness and efﬁciency of the proposed MA in extending WSN lifetime.
Future work may further consider different aspects of the proposed MA. First, given the above-stated advantages, the MA
may be applied to extending the WSN lifetime with additional constraints and objectives, such as network connectivity forthe communication range smaller than twice the sensing range and for point coverage [10]. Robustness and the dynamic
performance as some sensors fail will also be important topics of future work. Second, further enhancing the search abilityof the EA or the local enhancement operators will improve the performance of the MA in extending WSN lifetime.

Acknowledgments
The authors thank the editor and reviewers for their valuable comments and suggestions. This work was supported by the
National Science Council of Taiwan, under contract NSC98-2221-E-194-047.

References[1] Z. Abrams, A. Goel, S. Plotkin, Set k-cover algorithms for energy efﬁcient monitoring in wireless sensor networks, in: Proceedings of the Third
International Symposium on Information Processing in Sensor Networks, ACM Press, 2004, pp. 424–432.
[2] X. Ai, V. Srinivasan, C.K. Tham, DRACo: Distributed, robust an asynchronous coverage in wireless sensor networks, in: Proceedings of the Fourth AnnualIEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 2007, pp. 530–539.
[3] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks 38 (4) (2002) 393–422.
[4] B. Badrinath, J. Scholtz, M. Srivastava, K. Mills, V. Stanford, IEEE, IEEE Personal Communication, 2000 (Special issue on smart spaces and environments).
[5] P. Berman, G. Calinescu, C. Shah, A. Zelikovsky, Power efﬁcient monitoring management in sensor networks, in: Proceedings of the WirelessCommunications and Networking Conference, vol. 4, 2004, pp. 2329–2334.
[6] P. Berman, B. DasGupta, E. Sontag, On the complexities of some combinatorial problems in reverse engineering of protein and gene networks, Technicalreport, DIMACS, 2004.
[7] A.L. Buczak, Y. Jin, H. Darabi, M. Jafari, Genetic algorithm based sensor network optimization for target tracking, Intelligent Engineering Systems
Through Artiﬁcial Neural Networks 9 (1999) 349–354.
[8] M. Cardei, D.Z. Du, Improving wireless sensor network lifetime through power aware organization, Wireless Networks 11 (3) (2005) 333–340.
[9] M. Cardei, M.T. Thai, Y. Li, W. Wu, Energy-efﬁcient target coverage in wireless sensor networks, in: Proceedings of the IEEE INFOCOM, IEEE, 2005, pp.
1976–1984.
[10] M. Cardei, J. Wu, Energy-efﬁcient coverage problems in wireless ad-hoc sensor networks, Computer Communications 29 (2006) 413–420.
[11] L. Davis, Applying adaptive algorithms to epistatic domains, in: Proceedings of the Ninth International Joint Conference on Artiﬁcial Intelligence,
Morgan Kaufman, 1985, pp. 162–164.
[12] A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing, Natural Computing, Springer-Verlag, 2003.
[13] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.
[14] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, 1989.
[15] D.E. Goldberg, R. Lingle, Alleles, loci, and the traveling salesman problem, in: Proceedings of the First International Conference on Genetic Algorithms
and Their Applications, Lawrence Erlbaum Associates, Publishers, 1985, pp. 154–159.
[16] W.E. Hart, N. Krasnogor, J.E. Smith (Eds.), Recent Advances in Memetic Algorithms, Springer, 2004.
[17] Z. He, B.S. Lee, X.S. Wang, Aggregation in sensor networks with a user-provided quality of service goal, Information Sciences 178 (9) (2008) 2128–2149.
[18] W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efﬁcient communication protocol for wireless microsensor networks, in: Proceedings ofthe 33rd Annual Hawaii International Conference on System Sciences, 2000, pp. 1–10.
[19] R. Hinterding, Mapping, order-independent genes and the knapsack problem, in: Proceedings of the First IEEE Conference on Evolutionary
Computation, 1994, pp. 13–17.
[20] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor
networks, in: MobiCom ’00: Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, ACM, 2000, pp. 56–67.
[21] N. Krasnogor, J. Smith, A tutorial for competent memetic algorithms: model, taxonomy, and design issues, IEEE Transactions on Evolutionary
Computation 9 (5) (2005) 474–488.
[22] L. Krishnamachari, D. Estrin, S. Wicker, The impact of data aggregation in wireless sensor networks, in: Proceedings of the 22nd International
Conference on Distributed Computing Systems Workshop, 2002, pp. 575–578, 2002.
[23] C.C. Lai, C.K. Ting, R.S. Ko, An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications, in:Proceedings of the 2007 Congress on Evolutionary Computation, 2007, pp. 3531–3538.
[24] M.N. Le, Y.S. Ong, Y. Jin, B. Sendhoff, Lamarckian memetic algorithms: local optimum and connectivity structure analysis, Memetic Computing Journal
1 (3) (2009) 175–190.
[25] D. Li, K.D. Wong, Y.H. Hu, A.M. Sayeed, Detection, classiﬁcation, and tracking of targets, IEEE Signal Processing Magazine 19 (2002) 17–29.
[26] F. Marcelloni, M. Vecchio, Enabling energy-efﬁcient and lossy-aware data compression in wireless sensor networks by multi-objective evolutionary
optimization, Information Sciences 180 (10) (2010) 1924–1941.
[27] R. Meuth, M.H. Lim, Y.S. Ong, D.C. Wunsch II, A proposition on memes and meta-memes in computing for higher-order learning, Memetic Computing
Journal 1 (2) (2009) 85–100.

C.-K. Ting, C.-C. Liao / Information Sciences 180 (2010) 4818–4833

4833[28] H.D. Nguyen, I. Yoshihara, M. Yasunaga, Modiﬁed edge recombination operators of genetic algorithms for the traveling salesman problem, in:Proceedings of IEEE International Conference on Industrial Electronics, Control, and Instrumentation, 2000, pp. 2815–2820.
[29] C. Ok, S. Lee, P. Mitra, S. Kumara, Distributed routing in wireless sensor networks using energy welfare metric, Information Sciences 180 (9) (2010)
1656–1670.
[30] I.M. Oliver, D.J. Smith, J.R.C. Holland, A study of permutation crossover operators on the traveling salesman problem, in: Proceedings of the Second
International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum Associates, 1987, pp. 224–230.
[31] Y.S. Ong, N. Krasnogor, H. Ishibuchi, Special issue on memetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics 37(1) (2007) 2–5.
[32] Y.S. Ong, M.H. Lim, X.S. Chen, Research frontier: Memetic computation—past, present and future, IEEE Computational Intelligence Magazine 5 (2)(2010) 24–36.
[33] Y.S. Ong, M.H. Lim, N. Zhu, K.W. Wong, Classiﬁcation of adaptive memetic algorithms: a comparative study, IEEE Transactions on Systems, Man, andCybernetics—Part B: Cybernetics 36 (1) (2006) 141–152.
[34] V. Raghunathan, C. Schurgers, S. Park, M.B. Srivastava, Energy-aware wireless microsensor networks, IEEE Signal Processing 19 (2) (2002) 40–50.
[35] P.S. Sausen, M.A. Spohn, A. Perkusich, Broadcast routing in wireless sensor networks with dynamic power management and multi-coverage backbones,
Information Sciences 180 (5) (2010) 653–663.
[36] C. Schurgers, V. Tsiatsis, S. Ganeriwal, M. Srivastava, Optimizing sensor networks in the energy-latency-density design space, IEEE Transactions on
Mobile Computing 1 (1) (2002) 70–80.
[37] A. Sinha, Y.P. Chen, D.E. Goldberg, Designing efﬁcient genetic and evolutionary algorithm hybrids, in: W.E. Hart, N. Krasnogor, J. Smith (Eds.), Recent
Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, vol. 166, Springer, 2004, pp. 259–288.
[38] S. Slijepcevic, M. Potkonjak, Power efﬁcient organization of wireless sensor networks, in: Proceedings of the IEEE international conference oncommunications, vol. 2, 2001, pp. 472–476.
[39] T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, C. Whitley, A comparison of genetic sequencing operators, in: Proceedings of the FourthInternational Conference on Genetic Algorithms, Morgan Kaufman, 1991, pp. 69–76.
[40] J.A. Stine, G.D. Veciana, Improving energy efﬁciency of centrally controlled wireless data networks, Wireless Networks 8 (6) (2002) 681–700.
[41] C.K. Ting, Improving edge recombination through alternate inheritance and greedy manner, in: Evolutionary Computation in Combinatorial
Optimization – EvoCOP 2004, LNCS, vol. 3004, Springer-Verlag, 2004, pp. 210–219.
[42] P. Varshney, Distributed detection and data fusion, Springer-Verlag, 1996.
[43] D. Whitley, T. Starkweather, D. Fuquay, Scheduling problems and traveling salesman: the genetic edge recombination operator, in: Proceedings of theThird International Conference on Genetic Algorithms, Morgan Kaufman, 1989, pp. 133–140.
[44] X. Yan, F. Zhu, P.S. Yu, J. Han, Feature-based similarity search in graph structures, ACM Transactions of Database Systems 31 (4) (2006) 1418–1453.
[45] H. Zhang, J.C. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Ad Hoc & Sensor Wireless Networks 1 (2005) 89–124.