# Multiobjective Optimization for Topology and Coverage Control in Wireless Sensor Networks

Authors: Seyed Mahdi Jameii; Karim Faez; Mehdi Dehghan
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Coverage, connectivity, and network lifetime are important issues in wireless sensor networks (WSNs). Balancing the energy consumption in the network, reducing the transmission range of nodes, and density control of active nodes are approaches to extend the network lifetime. However, transmission range reduction and smaller number of active nodes can affect the network topology and may cause the network to be disconnected. So, there exist conflicts among lifetime, coverage, and connectivity. In this paper, these conflicting issues are considered and an evolutionary multiobjective optimization approach based on nondominated sorting genetic algorithm-II (NSGA-II) is proposed to optimize them. Simulation results demonstrate that the proposed algorithm can improve the network lifetime and coverage while maintaining the network connectivity.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are kind of wireless networks including a group of sensors which can be deployed rapidly and cheaply, and thereby they can be used for different purposes such as environment monitoring and object tracking [1]. WSNs play an important role in the improvement of the quality of people’s lives [2, 3]. Energy is an extremely critical resource in this kind of networks, thus prolonging the lifetime of network and making energy-efficient protocols are major design challenges in WSNs [4, 5]. Area coverage, point coverage [6], and barrier coverage [7] are three types of coverage in WSNs. Usually, in the case of random deployment, the number of deployed sensors is more than what is required [8]. It is not necessary to keep all sensor nodes in active mode simultaneously. We need a scheduling scheme which remains some sensors in active state to provide sensing services and puts other sensors to sleep state to conserve energy [9]. Sensor scheduling decreases the number of active sensors, avoids the channel collision, reduces the energy consumption in the network, and prolongs the network lifetime [10]. In addition, for ensuring that each sensor is able to communicate with the sink node, network connectivity should also be considered in WSNs [11, 12]. Balanced energy consumption in the network and efficient transmission ranges adjustment of the sensors are other approaches for energy conservation and prolonging the network lifetime [13]. Maximizing covered area, balanced energy consumption, minimizing the transmission range of nodes, minimizing the number of active nodes, and maintaining the connectivity of active nodes are critical issues in WSNs which are usually conflicting. The present paper aims to consider these conflicting issues simultaneously and proposes an evolutionary multiobjective optimization approach based on nondominated sorting genetic algorithm-II (NSGA-II) for optimizing them.The remainder of this paper is organized as follows. Section2 reviews some of the previous related works. Section 3 describes the related definitions and concepts. Section 4 gives network model and assumptions made in this paper. The proposed solution is presented in Section 5. In Section 6, the simulation results and discussions are provided and Section 7 concludes the paper.


## 2. Related Works

Network coverage, connectivity, and lifetime are important issues in WSNs. A lot of works have been done in recent years by the researchers for addressing these issues. Open geographic density control (OGDC) is one of the popular coverage algorithms [14]. In this approach, by controlling the density of the active sensors, the energy consumption can be reduced. In this algorithm, deterministic placement of the nodes is considered, but this kind of placement is only possible for the small-scale networks. The Coverage Configuration Protocol (CCP) is another coverage control protocol proposed in [15]. In this protocol, every node maintains the information of its neighbors and periodically broadcasts a hello message which contains current location of node and its status. The trade-off between the energy consumption and network coverage is not considered in this protocol. For example, in the case that only one intersecting point of a node is not covered by its neighbor, the protocol will activate this node. So, this protocol is not energy efficient in the case of the large-scale networks.The authors of [16] proposed approximation algorithms for both maximum lifetime and minimum cost coverage problems, but connectivity is not their concern. In [17], for modeling the area coverage in WSNs, a degree-constrained minimum-weight extension of the CDS (connected dominating set) problem called DCDS is provided and an approach based on learning automata called LAEEC is proposed for finding a near-optimal solution. The proposed solution balances the network load on the active sensors and improves the network coverage and lifetime. The authors of [18] used improved NSGA-II to optimize the network coverage and nodes utilization simultaneously. In [19] for solving the conflict among coverage and equilibrium of energy consumption in WSN, a multiobjective optimization strategy is proposed. The proposed strategy is based on a new evolutionary algorithm called multiobjective free search algorithm (MOFS). The problem of network coverage and connectivity is addressed in [20] and an efficient solution is proposed for maintaining coverage and preserving the connectivity of the network while minimizing the count of the active sensor nodes.The sensor deployment problem for WSNs is studied in [21, 22]. However, their objective is finding optimal locations for placing the sensors and maximizing the coverage rather than selecting covering sensor nodes from a randomly deployed sensor network. Additionally, connectivity has never been a requirement in these papers. The concept of multiobjective evolutionary algorithm based on decomposition (MOEA/D) is used in [23] for relocating the mobile nodes in a WSN with the goal of providing maximum sensing coverage area and minimizing the energy consumption. The goal of research presented in [24] is maintaining sensing coverage by activating a small number of sensors and consuming a small amount of energy in a WSN. The authors of [12] formulated maximum disjoint sets for maintaining coverage and connectivity problem in WSN and proposed a heuristic algorithm for solving it. A flexible algorithm presented in [25] uses an evolutionary computational approach to optimize connectivity and energy cost of WSNs in addition to coverage. The problem of positioning sensor nodes in WSN considering coverage with minimum energy consumption is studied in [26] and a multiobjective optimization approach is proposed for optimizing the energy consumption and coverage. The research presented in [27] used the characteristics of Voronoi diagram and direction-adjustable directional sensors and proposed a distributed greedy algorithm, which can improve the effective field coverage of directional sensor networks. The sensor field is divided into Voronoi cells and the sensor working direction is evaluated based on Voronoi vertices. Considering the coverage contribution of convex polygonal cell of sensors and the coverage overlap of direction select between neighbor sensors, the working direction is adjusted and controlled, so as to improve the overall sensing field coverage ratio in the sensor network environment without global information. The authors of [28] proposed a multiobjective optimization algorithm to efficiently schedule the nodes of a wireless sensor network and to optimize energy consumption, lifetime, and coverage.The authors of [29] formulated the sensor node deployment task as a constrained multiobjective optimization problem with the aims of maximizing the area of coverage and minimizing the number of deployed sensor nodes. They used a decomposition approach for converting the problem of approximation of the Pareto fronts into a number of single-objective optimization problems. The authors of [30] proposed a multiobjective hybrid optimization algorithm to solve the dynamic coverage and connectivity problem (DCCP) in flat WSNs. In [31], an algorithm based on Euclidean distance called CWSC is proposed to k-cover the sensing region while minimizing the number of working sensors. The goal of the research presented in [32] is addressing the network lifetime maximization problem with connectivity and coverage constraints by scheduling the activity of sensors.Although all of the above-mentioned researches have achieved the coverage requirement, some of them have not considered the network lifetime [12, 20, 22, 27] and the network connectivity [16, 21–23]. Some works such as [14, 15, 17–20, 24] require that the transmission range is at least twice the size of the sensing range; otherwise, the connectivity may not be guaranteed.All of the above studies except [25] have not considered the transmission range adjustment for sensor nodes to maximize the network lifetime. These works assumed the same transmission range for all sensors. Among the above-mentioned works, only [19] considered the balanced energy consumption in the network.In this paper, we propose a multiobjective optimization approach to optimize the area coverage, network lifetime, network connectivity, transmission range adjustment of nodes, and balanced energy consumption simultaneously in WSN without any sensing range or transmission range restriction.


## 3. Related Definitions and Concepts

### 3.1. Multiobjective Optimization Problems

A multiobjective optimization problem (MOP) is stated as follows [33]:
(1)MinimizeormaximizeF(x)=(F1(x),…,Fm(x))
subjected to x∈Ω, where Ω⊂Rn is the decision space, F:Ω→Rm consists of m real-valued objective function, and Rm is objective space. In some cases, a MOP has various equality and inequality constraints as follows:
(2)gix≤0,i=1,…,p,hjx=0,j=p+1,…,q.
In the case that optimization problems involve constraints, the search space X can be defined as follows:
(3)Ω∈x∣x∈X,xmeetsconstrainsC1,…,Cq,
where X is the base search space and x is a solution of the feasible region Ω that satisfies all q constraints, that is, C1,…,Cq. The solutions that satisfy all constraints are called feasible and those that do not are infeasible. In a multiobjective optimization problem where there are m objectives F1,…,Fm for minimization, we have the following definitions:Definition 1.
Assume thatx and y are two decision variables; x is said to dominate y, denoted by x<y, if and only if Fi(x)≤Fi(y) for every i∈{1,2,…,m} and Fi(x)≤Fi(y) for at least one index j∈{1,2,…,m}.Definition 2.
x
*
∈
Ω is said to be Pareto-optimal (or nondominated) if there is no other x∈Ω so that x dominates x*. The set of all Pareto-optimal solutions in the decision space is called the Pareto-optimal set (PS). The image of the PS in the objective space is called the Pareto-optimal front (PF).
Figure1(a) illustrates a PF with m=2. The Pareto-optimal solutions in the PF (marked as asterisk) provide better values for objective functions than any other solution in the objective space. The ideal solution (marked as rectangle) provides the minimum objective values and it is often considered unreachable. The remaining solutions (marked as solid circles) are all dominated by at least one solution of the PF. In Figure 1(b), the bold curve indicates the PF of a constrained MOP. The solid circles are the feasible solutions in the feasible region and the remaining solutions outside the feasible region (marked as triangle) are considered infeasible.The PF of MOP: (a) unconstrained MOP and (b) constrained MOP.
(a)
PF of unconstrained MOP
(b)
PF of constrained MOP


### 3.2. NSGA-II Algorithm

There are several well-known multiobjective genetic algorithms (MOGAs). NSGA-II [34] is one of the most popular algorithms. By introducing the fast nondominated sorting approach, binary crowding tournament selection, and elitism, the Pareto-optimal front can be searched effectively. NSGA-II has a diversity-preserving mechanism which assures convergence towards the Pareto-optimal front without losing solution diversity. The standard NSGA-II algorithm works as follows [34].Initially, a random populationDt(t=0) is created and is sorted into different nondominance levels. For each solution a fitness value equal to its nondominance level is assigned. For creating an offspring population Et of size N, some operators such as binary tournament selection, mutation, and recombination are used. Then the following steps will be repeated until the number of generations reaches the maximum number of generations.Step 1.
Combine parent and offspring populations to createPt=Dt∪Et. Perform a fast nondominated sorting in Pt according to the algorithm shown in Algorithm 1 and identify different fronts Fri, i=1,2,….Algorithm 1:The pseudocode of the fast nondominated sorting algorithm.
Fast non-dominated sorting algorithm [34]
Input: population P
Output: The non-dominated fronts (Fr1, Fr2,…)
For eachp∈P
For each q∈P
If (p<q) then
Sp=Sp∪{q}
else if (q<p) then
np=np+1
ifnp=0 then
F1=F1∪{p}
i
=
1
whileFi<>Ø
H=Ø
For eachp∈Fri
For eachq∈Sp
nq=nq-1
ifnq=0 the H=H∪{q}
i
=
i
+
1
F
r
i
=
HStep 2.
Set a new populationDt+1=Ø. Set counter i=1.
WhileDt+1+Fri<N, do Dt+1=Dt+1∪Fri and i=i+1.Step 3.
Select (N-Dt+1) most widely spread solutions from Fri using the binary crowding tournament selection operator and insert them into Dt+1.Step 4.
Create an offspring populationEt+1 from Dt+1 by using the binary crowding tournament selection, crossover, and mutation operators. Set t=t+1.
The process of nondominated sorting and filling the populationDt+1 steps can be performed together. In Step 3, the crowding-sorting of the solutions in front Fri, which is the last front that could not be completely accommodated, is performed by using a crowded-distance metric.
The crowding comparison operator compares two solutions and returns the winner of the tournament. The winner is selected based on two attributes: the nondominance rankingri and the local crowding distance di in the population. This crowding distance attribute of a solution i is a measure of the search space around i, which is not occupied by any other solution in the population. Based on ri and di, the binary crowding tournament selection operator works as follows.
A solutioni wins a tournament over another solution j if any of the following conditions is true.(1)
Ifri<rj (this assures that the selected solution lies on a better nondominated front).(2)
Ifri<rj and di<dj (this is applied when both solutions lie on the same front and the above condition cannot be applied; in this case, the solution residing in a less crowded area with a larger di wins).


### 3.3. Dynamic Crowding Distance (DCD) Algorithm

Horizontal diversity of Pareto-front is very important in MOEAs and it is realized by removing excess individuals in the nondominated set. For removing the excess individuals, NSGA-II uses crowding distance (CD) measure. The individuals with lower value of CD have a high priority to be removed in the removal process. The value of CD is calculated using(4)CDi=1Nobj∑z=1NobjFi+1z-Fi-1z,
where Nobj is the number of objectives, Fi+1z is the zth objective of the i+1th individual, and Fi-1z is the zth objective of the i-1th individual after sorting the population according to CD value. The major drawback of crowding distance is the lack of uniform diversity in obtained nondominated solutions. To overcome this problem, DCD method is suggested in [35]. The DCD of individuals is calculated based on
(5)DCDi=CDilog⁡⁡(1/Var⁡i),
where CDi is calculated by (4) and Var⁡i is calculated based on
(6)Var⁡i=1Nobj∑z=1NobjFi+1z-Fi-1z-CDi2.Var⁡i is the variance of CDs of individuals which are neighbors of the ith individual.


## 3.1. Multiobjective Optimization Problems

A multiobjective optimization problem (MOP) is stated as follows [33]:
(1)MinimizeormaximizeF(x)=(F1(x),…,Fm(x))
subjected to x∈Ω, where Ω⊂Rn is the decision space, F:Ω→Rm consists of m real-valued objective function, and Rm is objective space. In some cases, a MOP has various equality and inequality constraints as follows:
(2)gix≤0,i=1,…,p,hjx=0,j=p+1,…,q.
In the case that optimization problems involve constraints, the search space X can be defined as follows:
(3)Ω∈x∣x∈X,xmeetsconstrainsC1,…,Cq,
where X is the base search space and x is a solution of the feasible region Ω that satisfies all q constraints, that is, C1,…,Cq. The solutions that satisfy all constraints are called feasible and those that do not are infeasible. In a multiobjective optimization problem where there are m objectives F1,…,Fm for minimization, we have the following definitions:Definition 1.
Assume thatx and y are two decision variables; x is said to dominate y, denoted by x<y, if and only if Fi(x)≤Fi(y) for every i∈{1,2,…,m} and Fi(x)≤Fi(y) for at least one index j∈{1,2,…,m}.Definition 2.
x
*
∈
Ω is said to be Pareto-optimal (or nondominated) if there is no other x∈Ω so that x dominates x*. The set of all Pareto-optimal solutions in the decision space is called the Pareto-optimal set (PS). The image of the PS in the objective space is called the Pareto-optimal front (PF).
Figure1(a) illustrates a PF with m=2. The Pareto-optimal solutions in the PF (marked as asterisk) provide better values for objective functions than any other solution in the objective space. The ideal solution (marked as rectangle) provides the minimum objective values and it is often considered unreachable. The remaining solutions (marked as solid circles) are all dominated by at least one solution of the PF. In Figure 1(b), the bold curve indicates the PF of a constrained MOP. The solid circles are the feasible solutions in the feasible region and the remaining solutions outside the feasible region (marked as triangle) are considered infeasible.The PF of MOP: (a) unconstrained MOP and (b) constrained MOP.
(a)
PF of unconstrained MOP
(b)
PF of constrained MOP


## 3.2. NSGA-II Algorithm

There are several well-known multiobjective genetic algorithms (MOGAs). NSGA-II [34] is one of the most popular algorithms. By introducing the fast nondominated sorting approach, binary crowding tournament selection, and elitism, the Pareto-optimal front can be searched effectively. NSGA-II has a diversity-preserving mechanism which assures convergence towards the Pareto-optimal front without losing solution diversity. The standard NSGA-II algorithm works as follows [34].Initially, a random populationDt(t=0) is created and is sorted into different nondominance levels. For each solution a fitness value equal to its nondominance level is assigned. For creating an offspring population Et of size N, some operators such as binary tournament selection, mutation, and recombination are used. Then the following steps will be repeated until the number of generations reaches the maximum number of generations.Step 1.
Combine parent and offspring populations to createPt=Dt∪Et. Perform a fast nondominated sorting in Pt according to the algorithm shown in Algorithm 1 and identify different fronts Fri, i=1,2,….Algorithm 1:The pseudocode of the fast nondominated sorting algorithm.
Fast non-dominated sorting algorithm [34]
Input: population P
Output: The non-dominated fronts (Fr1, Fr2,…)
For eachp∈P
For each q∈P
If (p<q) then
Sp=Sp∪{q}
else if (q<p) then
np=np+1
ifnp=0 then
F1=F1∪{p}
i
=
1
whileFi<>Ø
H=Ø
For eachp∈Fri
For eachq∈Sp
nq=nq-1
ifnq=0 the H=H∪{q}
i
=
i
+
1
F
r
i
=
HStep 2.
Set a new populationDt+1=Ø. Set counter i=1.
WhileDt+1+Fri<N, do Dt+1=Dt+1∪Fri and i=i+1.Step 3.
Select (N-Dt+1) most widely spread solutions from Fri using the binary crowding tournament selection operator and insert them into Dt+1.Step 4.
Create an offspring populationEt+1 from Dt+1 by using the binary crowding tournament selection, crossover, and mutation operators. Set t=t+1.
The process of nondominated sorting and filling the populationDt+1 steps can be performed together. In Step 3, the crowding-sorting of the solutions in front Fri, which is the last front that could not be completely accommodated, is performed by using a crowded-distance metric.
The crowding comparison operator compares two solutions and returns the winner of the tournament. The winner is selected based on two attributes: the nondominance rankingri and the local crowding distance di in the population. This crowding distance attribute of a solution i is a measure of the search space around i, which is not occupied by any other solution in the population. Based on ri and di, the binary crowding tournament selection operator works as follows.
A solutioni wins a tournament over another solution j if any of the following conditions is true.(1)
Ifri<rj (this assures that the selected solution lies on a better nondominated front).(2)
Ifri<rj and di<dj (this is applied when both solutions lie on the same front and the above condition cannot be applied; in this case, the solution residing in a less crowded area with a larger di wins).


## 3.3. Dynamic Crowding Distance (DCD) Algorithm

Horizontal diversity of Pareto-front is very important in MOEAs and it is realized by removing excess individuals in the nondominated set. For removing the excess individuals, NSGA-II uses crowding distance (CD) measure. The individuals with lower value of CD have a high priority to be removed in the removal process. The value of CD is calculated using(4)CDi=1Nobj∑z=1NobjFi+1z-Fi-1z,
where Nobj is the number of objectives, Fi+1z is the zth objective of the i+1th individual, and Fi-1z is the zth objective of the i-1th individual after sorting the population according to CD value. The major drawback of crowding distance is the lack of uniform diversity in obtained nondominated solutions. To overcome this problem, DCD method is suggested in [35]. The DCD of individuals is calculated based on
(5)DCDi=CDilog⁡⁡(1/Var⁡i),
where CDi is calculated by (4) and Var⁡i is calculated based on
(6)Var⁡i=1Nobj∑z=1NobjFi+1z-Fi-1z-CDi2.Var⁡i is the variance of CDs of individuals which are neighbors of the ith individual.


## 4. Network Model and Assumptions

The sensor network consists of a static resource-rich sink node andN stationary resource-constrained sensor nodes deployed randomly with uniform distribution over a finite, two-dimensional region A. The transmission range of these nodes is also limited such that the entire network cannot be traversed in a single hop. Sensor nodes are assumed to be heterogeneous and each sensor node can adjust its radio transmission range Rt to vary from 0 to the maximum transmit range Rt(max). We assumed eight predefined transmission range levels for each sensor. We also assumed that all sensor nodes have the same sensing range Rs and each node knows its position and also the positions of its neighbors within its transmission range.The sensing range and the transmission ranges of sensor nodes are assumed as perfect disks which means that a node can sense the area points which are within a distance ofRs from the node.RegionA is divided into some uniform consecutive grids to make the coverage problem more computationally manageable. We have assumed a cluster-based architecture for WSN and each cluster is modeled as a mesh of grids, one cluster head, and NC member of nodes with different transmission range. This model is depicted in Figure 2.Figure 2
Example of area coverage in a cluster. The cluster is modeled as a mesh of grids. For a sensor node, the sensing rangeRs and the transmission range Rt are depicted.We assume a continuous monitoring application and all sensor nodes send their sensed data to its cluster head periodically. All cluster heads transmit their data to a base station periodically. The cluster formation and routing are not considered in this paper. We considered area coverage in each cluster and modeled the monitoring status of a grid which centered at (x′,y′) as follows:
(7)gridx′,y′=1if∃j∈1,…,N,d(xj,yj),(x′,y′)≤Rs,0otherwise,
where 1 indicates that this grid is covered and 0 otherwise.For ensuring that there are no collisions during data communication, SMAC [36] is used as medium access control protocol. Also, we adopt the path loss communication model as in [37]. All the nodes in the network have the same initial energy. Equation (8) calculates the residual energy of sensor i, at time t [13]:
(8)Eit=Eit-1-Etxit+Erxit+Es,
where Etxit and Erxit are transmission and reception energy consumed by sensor i, respectively, and are calculated based on
(9)Etxit=rit+k*pi*amp,Erxit=rit*Ect.Es is the total energy consumed by sensor i for sensing and processing with a fixed sensing range Rs in one time slot, ri(t) is the amount of bits that i receives and relays towards the cluster head at time t, k is the amount of data generated by i which should be forwarded to the cluster head, amp is the energy consumption of the power amplifier, and Ect is the required energy for receiving a bit of data.


## 5. Multiobjective Optimization Approach

This section describes the proposed multiobjective optimization algorithm for transmission range adjustment, scheduling, coverage and connectivity control called TASCC. TASCC is proposed based on NSGA-II to optimize coverage, number of active nodes, and balanced energy consumption while maintaining the connectivity in WSNs. As mentioned earlier, we assumed a cluster-based architecture and the network lifetime is scheduled into rounds.Since the cluster heads consume more energy, for balancing the residual energy of nodes, new cluster heads are chosen in each round and then, the new clusters will be formed. Each cluster head is responsible for calculating the transmission range and determining the scheduling status of its member nodes by executing the TASCC algorithm. The final results calculated by the cluster heads are sent to their member nodes and each member node will adjust its transmission range and scheduling status.


### 5.1. Multiobjective Formulation of TASCC

The TASCC is formulated as a multiobjective optimization problem as follows.Decision Variable 1. Scheduling status of sensor j is defined as follows:
(10)Statusj=1,ifsensorjisactive0,otherwise.Decision Variable 2. Transmission range of sensor j (Rtj), 0≤Rtj≤Rt(max⁡).Objectives. Maximizing the coverage rate, minimizing the percentage of active sensor nodes, and minimizing the unbalanced energy consumption.Constraint. Network connectivity: the network connectivity means that there is at least one path between each sensor node and the sink node.Objective 1. Minimizing the rate of the uncovered area.At first, the rate of area coverage which is the percentage of the covered grids over the total grids is formulated as follows:(11)F1′=CoverageRate=∑x′∈X∑y′∈Ygrid(x′,y′)G,
where (X,Y) is the center of grids coordinates in the cluster, G is the total number of grids in the cluster, and gridx′,y′ is calculated according to (7).To translate this objective to a minimization objective, the rate of the uncovered area is defined as follows:(12)F1=1-F1′.Objective 2. Minimizing the unbalanced energy consumption which is evaluated as follows:
(13)F2=Eunbalanced=Max⁡⁡Ei-Min⁡EiMax⁡Ei,llllllllllforeachnodeiinthecluster,
where Ei is the residual energy of sensor i and is calculated according to (8). The higher value of Eunbalanced means the more unbalanced energy consumption.Objective 3. Minimizing the number of active sensors is evaluated according to
(14)F3=∑j∈NCStatusj,
where NC is the total number of sensors in the cluster.The optimization problem is defined as follows:(15)F=ArgminF1,F2,F3.


### 5.2. Genetic Representation of the Solutions

Each solutionX consists of NC items. Each item j represents an individual sensor node j and has two parts: statusj and Rtj, which represent the scheduling status of sensor node j and the transmission range of sensor j, respectively. So, we need four bits for each item: the first bit is used to describe the scheduling status of the sensor node and the three remaining bits describe one of the eight predefined values of transmission range. This genetic representation of solution is depicted in Figure 3.Figure 3
Genetic representation of solution.For a sensor node, the possibilities of four-bit encoding scheme are represented in Table1.Table 1
The possibilities of four-bit encoding scheme.
Binary encoding
Description
0000
Being an inactive sensor
1000
Being an active sensor operating in a first (lowest) level of transmission range
1001
Being an active sensor operating in a second level of transmission range
⋮
1111
Being an active sensor operating in a last (highest) level of transmission range


### 5.3. TASCC Algorithm

At first, the algorithm generates an initial population of sizeM. In each solution in the initial population, G sensor nodes are activated uniformly and randomly (G is the number of grids in the cluster). To every activated sensor j in the initial solution, a transmission range level Rtj is assigned as (16) such that it reaches the sensor k which is its closest neighbor and is closer to cluster head compared to j:(16)Rtj=dj,clusterheadclusterheadisj,sclosestneighboranddj,clusterhead≤Rmax⁡dj,kXk,Ykisj,sclosestneighbor,anddistancek,clusterhead<distancej,clusterhead,Rtk≠0,anddj,k≤Rmax⁡0otherwise.Each solution in the initial population is evaluated using the objective functionsF1, F2, F3 and connectivity constraint mentioned earlier. Then, offspring population will be created from the existing (parent) population using the crowded tournament selection, crossover, and mutation operator.We use two-point crossover operator with randomly selected crossing points in our solution. Figure4 illustrates the results of applying two-point crossover on two sample solutions with six parts.Figure 4
Applying two-point crossover.The mutation type used in this paper depends on the selected bit in the solution to be muted. If the selected bit is the first bit of an item in the solution (represents the scheduling status of node), the mutation operator works as follows.At first, the minimum number of required active sensors (Smin⁡) for satisfying the requested coverage rate is calculated using
(17)Smin⁡=Ac·dcov⁡As,
where Ac is the area of the cluster which will be monitored, As is the circular sensing area of a sensor, and dcov⁡ is the requested coverage rate by the designer. Since circular coverage is assumed for each node, we have
(18)As=πRs2.Before applying mutation operator on the solutionS, the number of active sensors in S (Sactive) is calculated and then, based on Sactive and Smin⁡, the mutation operator will apply on it by considering the following rules.IfSactive<Smin⁡ and the selected bit is 0, then it will be changed to 1;
else ifSactive>Smin⁡ and the selected bit is 1, then it will be changed to 0;
else the mutation operator should select another bit for mutation.Regarding these rules, it is obvious that this type of mutation employs problem-based knowledge and will reduce the energy consumption of the network and improve the network coverage.If the selected bit for mutation is not the first bit of an item on the solution, we use the classical mutation which swaps the selected bit (0 becomes 1 and vice versa).After creating the offspring population, it combined with the parent population and the new population will be created. Then, the fast nondominated sorting algorithm is performed on this combined population to identify different frontsFrii=1,2,…. Then the new population is created and step by step contains the solutions of different nondominated fronts. At first, it contains the solutions of the best nondominated front (Fr1) and continues with solutions of the second nondominated and so on.The new population of sizeM may not accommodate all fronts of the combined population with size 2M. So, if all the solutions of the current front cannot be accommodated in the new population, the DCD values of the solutions in this front are calculated based on (5) discussed in Section 3. Then, the solutions will be sorted in descending order according to DCD values and the required solutions for new population will be selected from the first of this front. The above-mentioned process continues until the number of generations reaches the maximum number of generations. The pseudocode of the TASCC algorithm is outlined in Algorithm 2.Algorithm 2:The pseudocode of the TASCC algorithm.
TASCC Algorithm
Input: Network parameters (Ac, NC, dcov⁡, G, Rs, Rt(max),…)
Output: Non-dominated solutions.
Step  1. Choose population size M, crossover probability (Pc) and mutation probability (Pm), crossover and mutation index,
maximum number of generations (genmax).
Set the generation countt=0;
Step  2. Generate an initial population Dt as follow:
Fori=1,…,M do
Step  2.1. Activate G sensor nodes uniformly and randomly in solution of population Dt;
Step  2.2. For every activated sensor j in solution i, assign transmission range level (Rtj) according to (16)
Step  3. Evaluate each solution in Dt using objective functions and connectivity constrain;
Step  4. Apply the crowded tournament selection, mutation and crossover operators to create offspring population Et from Dt;
Step  5. Set Pt=Dt∪Et;
Step  6. Do fast non-dominated sorting on Pt according to Algorithm 1, resulting non-dominated fronts Fr1, Fr2,…;
Step  7. Set Dt+1=Ø; i=1;
While|Dt+1|+|Fri|<M do
(Dt+1=Dt+1∪Fri,i=i+1);
If|Dt+1|<M then
Calculate DCD values of the solutions inFri and sort the solutions in descending order according to DCD values;
Add the firstM-|Dt+1| solution from Fri to Dt+1;
Ift < genmax then set t=t+1 and go to Step  3.


## 5.1. Multiobjective Formulation of TASCC

The TASCC is formulated as a multiobjective optimization problem as follows.Decision Variable 1. Scheduling status of sensor j is defined as follows:
(10)Statusj=1,ifsensorjisactive0,otherwise.Decision Variable 2. Transmission range of sensor j (Rtj), 0≤Rtj≤Rt(max⁡).Objectives. Maximizing the coverage rate, minimizing the percentage of active sensor nodes, and minimizing the unbalanced energy consumption.Constraint. Network connectivity: the network connectivity means that there is at least one path between each sensor node and the sink node.Objective 1. Minimizing the rate of the uncovered area.At first, the rate of area coverage which is the percentage of the covered grids over the total grids is formulated as follows:(11)F1′=CoverageRate=∑x′∈X∑y′∈Ygrid(x′,y′)G,
where (X,Y) is the center of grids coordinates in the cluster, G is the total number of grids in the cluster, and gridx′,y′ is calculated according to (7).To translate this objective to a minimization objective, the rate of the uncovered area is defined as follows:(12)F1=1-F1′.Objective 2. Minimizing the unbalanced energy consumption which is evaluated as follows:
(13)F2=Eunbalanced=Max⁡⁡Ei-Min⁡EiMax⁡Ei,llllllllllforeachnodeiinthecluster,
where Ei is the residual energy of sensor i and is calculated according to (8). The higher value of Eunbalanced means the more unbalanced energy consumption.Objective 3. Minimizing the number of active sensors is evaluated according to
(14)F3=∑j∈NCStatusj,
where NC is the total number of sensors in the cluster.The optimization problem is defined as follows:(15)F=ArgminF1,F2,F3.


## 5.2. Genetic Representation of the Solutions

Each solutionX consists of NC items. Each item j represents an individual sensor node j and has two parts: statusj and Rtj, which represent the scheduling status of sensor node j and the transmission range of sensor j, respectively. So, we need four bits for each item: the first bit is used to describe the scheduling status of the sensor node and the three remaining bits describe one of the eight predefined values of transmission range. This genetic representation of solution is depicted in Figure 3.Figure 3
Genetic representation of solution.For a sensor node, the possibilities of four-bit encoding scheme are represented in Table1.Table 1
The possibilities of four-bit encoding scheme.
Binary encoding
Description
0000
Being an inactive sensor
1000
Being an active sensor operating in a first (lowest) level of transmission range
1001
Being an active sensor operating in a second level of transmission range
⋮
1111
Being an active sensor operating in a last (highest) level of transmission range


## 5.3. TASCC Algorithm

At first, the algorithm generates an initial population of sizeM. In each solution in the initial population, G sensor nodes are activated uniformly and randomly (G is the number of grids in the cluster). To every activated sensor j in the initial solution, a transmission range level Rtj is assigned as (16) such that it reaches the sensor k which is its closest neighbor and is closer to cluster head compared to j:(16)Rtj=dj,clusterheadclusterheadisj,sclosestneighboranddj,clusterhead≤Rmax⁡dj,kXk,Ykisj,sclosestneighbor,anddistancek,clusterhead<distancej,clusterhead,Rtk≠0,anddj,k≤Rmax⁡0otherwise.Each solution in the initial population is evaluated using the objective functionsF1, F2, F3 and connectivity constraint mentioned earlier. Then, offspring population will be created from the existing (parent) population using the crowded tournament selection, crossover, and mutation operator.We use two-point crossover operator with randomly selected crossing points in our solution. Figure4 illustrates the results of applying two-point crossover on two sample solutions with six parts.Figure 4
Applying two-point crossover.The mutation type used in this paper depends on the selected bit in the solution to be muted. If the selected bit is the first bit of an item in the solution (represents the scheduling status of node), the mutation operator works as follows.At first, the minimum number of required active sensors (Smin⁡) for satisfying the requested coverage rate is calculated using
(17)Smin⁡=Ac·dcov⁡As,
where Ac is the area of the cluster which will be monitored, As is the circular sensing area of a sensor, and dcov⁡ is the requested coverage rate by the designer. Since circular coverage is assumed for each node, we have
(18)As=πRs2.Before applying mutation operator on the solutionS, the number of active sensors in S (Sactive) is calculated and then, based on Sactive and Smin⁡, the mutation operator will apply on it by considering the following rules.IfSactive<Smin⁡ and the selected bit is 0, then it will be changed to 1;
else ifSactive>Smin⁡ and the selected bit is 1, then it will be changed to 0;
else the mutation operator should select another bit for mutation.Regarding these rules, it is obvious that this type of mutation employs problem-based knowledge and will reduce the energy consumption of the network and improve the network coverage.If the selected bit for mutation is not the first bit of an item on the solution, we use the classical mutation which swaps the selected bit (0 becomes 1 and vice versa).After creating the offspring population, it combined with the parent population and the new population will be created. Then, the fast nondominated sorting algorithm is performed on this combined population to identify different frontsFrii=1,2,…. Then the new population is created and step by step contains the solutions of different nondominated fronts. At first, it contains the solutions of the best nondominated front (Fr1) and continues with solutions of the second nondominated and so on.The new population of sizeM may not accommodate all fronts of the combined population with size 2M. So, if all the solutions of the current front cannot be accommodated in the new population, the DCD values of the solutions in this front are calculated based on (5) discussed in Section 3. Then, the solutions will be sorted in descending order according to DCD values and the required solutions for new population will be selected from the first of this front. The above-mentioned process continues until the number of generations reaches the maximum number of generations. The pseudocode of the TASCC algorithm is outlined in Algorithm 2.Algorithm 2:The pseudocode of the TASCC algorithm.
TASCC Algorithm
Input: Network parameters (Ac, NC, dcov⁡, G, Rs, Rt(max),…)
Output: Non-dominated solutions.
Step  1. Choose population size M, crossover probability (Pc) and mutation probability (Pm), crossover and mutation index,
maximum number of generations (genmax).
Set the generation countt=0;
Step  2. Generate an initial population Dt as follow:
Fori=1,…,M do
Step  2.1. Activate G sensor nodes uniformly and randomly in solution of population Dt;
Step  2.2. For every activated sensor j in solution i, assign transmission range level (Rtj) according to (16)
Step  3. Evaluate each solution in Dt using objective functions and connectivity constrain;
Step  4. Apply the crowded tournament selection, mutation and crossover operators to create offspring population Et from Dt;
Step  5. Set Pt=Dt∪Et;
Step  6. Do fast non-dominated sorting on Pt according to Algorithm 1, resulting non-dominated fronts Fr1, Fr2,…;
Step  7. Set Dt+1=Ø; i=1;
While|Dt+1|+|Fri|<M do
(Dt+1=Dt+1∪Fri,i=i+1);
If|Dt+1|<M then
Calculate DCD values of the solutions inFri and sort the solutions in descending order according to DCD values;
Add the firstM-|Dt+1| solution from Fri to Dt+1;
Ift < genmax then set t=t+1 and go to Step  3.


## 6. Simulation Results and Discussions

In this section, we evaluate the performance of the TASCC algorithm via simulations. Simulations were performed using the NS-2 simulator. The simulations are conducted for different number of sensor nodes in the network and the averages of the results are depicted.


### 6.1. Simulation Settings

Experiments are conducted on a 100* 100 square meter region. We consider the grids of size 2 m * 2 m, and if centers of all grids are covered, we assume that the entire region is covered. The simulation parameters are summarized in Table 2.Table 2
Simulation parameters.
Parameter
Value
Field dimensions
(100×100) m2
R
s
10 m
MaxRt
35 m
Levels of transmission ranges (8 levels)
0,5
,
10,15
,
…
,
35
genmax
200
Amp
100 pJ/bit/m2
E
s
5 nJ/bit
E
rx
5 nJ/bit
E
tx
50 nJ/bit
E
init
2 J
Population size
100
Mutation  probability
0.2
Crossover probability
0.9


### 6.2. Results

We consider the following metrics for evaluation and compare the TASCC algorithm with the OGDC [14], CCP [15], LAEEC [17], and ECCA [18]:(1)
coverage rate of the network;(2)
connectivity of the network;(3)
number of active sensors;(4)
balanced energy consumption;(5)
network lifetime.Experiment 1.
In this experiment, 100 sensor nodes are deployed in the region and the coverage rate of the network is evaluated. A grid is said to be covered, if the center of that grid is covered at least by a sensor node. The coverage rate of the monitoring region versus the number of active sensors at different generations is shown in Figure5. As can be seen in this figure, there is a trade-off between the coverage rate and the number of active sensors. The coverage rate is significantly increased as the number of active sensors increases. At 200th generation, better coverage rate can be obtained with less number of active sensors compared to the other generations. For example, the required active sensors to obtain the coverage rate of 0.9 at generations 50, 100, and 200 are about 50, 40, and 28, respectively.
Figure6 plots the coverage rate versus the number of active sensors for different algorithms. As shown in this figure, with the same number of active sensors, TASCC can obtain a higher coverage rate than other algorithms because TASCC considers the number of active sensors and the coverage rate simultaneously. The coverage rate of CCP decreases with increase in the number of working sensors. This is because a large number of message exchanges are required in CCP to maintain neighborhood information. In the case of low density of active sensors, OGDC provides less coverage rate rather than the other protocols. This is due to the fact that OGDC suffers from many redundant active sensors.Figure 5
The coverage rate versus the number of active sensors at various generations.Figure 6
The coverage rate versus the number of active sensors for different algorithms.Experiment 2.
In this experiment, we consider different number of deployed nodes and the coverage rate of 0.9 and measure the required number of active nodes for satisfying this coverage rate for different algorithms. The results of this experiment are presented in Figure7. According to the results shown in this figure, it can be seen that TASCC has the minimum number of active nodes as compared to the other protocols. With the increasing of number of deployed sensors, TASCC maintains the same number of active sensors (about 25 sensors). This is because the number of required active sensors is independent of the density of the deployed sensors while for other algorithms, the number of required active nodes increases as the number of deployed sensors increases.Figure 7
The number of active sensors versus the number of deployed sensors.Experiment 3.
In this experiment, we consider different number of deployed nodes and the coverage rate of 0.9 and compare the lifetime of the proposed algorithm with other algorithms. The network lifetime is defined as the round when the first node depletes its energy. The changes in the network lifetime are shown in Figure8 where the number of sensors changes from 50 to 200. It can be seen that for all algorithms, as the network size increases, the network lifetime increases too. It is observed that the proposed algorithm has the longest lifetime. This is because in the proposed algorithm, in addition to density control of active nodes, balancing the energy consumption in the network and adjusting the transmission range of nodes result in extending the network lifetime. As mentioned earlier, in other algorithms, the transmission range should be at least twice the size of the sensing range and this may cause more energy consumption and shortening of the network lifetime. The network lifetime in CCP is much shorter than in other algorithms. This is because CCP periodically broadcasts hello messages, and thus more energy will be consumed.Figure 8
Network lifetime versus the number of deployed sensors.Experiment 4.
In this experiment, 200 sensor nodes are deployed in the region and the residual energy of these nodes is measured after 200 generations in order to calculate the unbalanced energy consumption of different algorithms according to (13). The value of this parameter varies between 0 and 1. At the ideal case, the maximum and the minimum residual energy of the nodes will be the same and the value of the unbalanced energy consumption parameter will be 0. On the other hand, in the worst case, the energy of at least one sensor will be depleted while some other nodes are full of energy and according to (13), the value of this parameter will be 1. Figure 9 shows the unbalanced energy consumptions for different algorithms. Based on the results, we find that the unbalanced energy consumption in the proposed algorithm is lower than the other algorithms. This is due to the fact that the proposed algorithm, unlike the other algorithms, considers the balanced energy consumption as an objective and avoids the rapid depletion of the energy and periodically changes the active sensors to balance the residual energy of nodes.Figure 9
Unbalanced energy consumption for different algorithms.Experiment 5.
In this experiment, different network sizes are considered and the number of unconnected sensors in the proposed algorithm is calculated and compared with other algorithms. Figure10 shows the result of this experiment. As shown in this figure, TASCC outperforms other algorithms in terms of connectivity. This is because the proposed algorithm unlike the other algorithms can dynamically adjust the transmission range of the sensors to maintain the connectivity and reduce the unconnected sensors.Figure 10
The number of unconnected sensors versus the network size.


## 6.1. Simulation Settings

Experiments are conducted on a 100* 100 square meter region. We consider the grids of size 2 m * 2 m, and if centers of all grids are covered, we assume that the entire region is covered. The simulation parameters are summarized in Table 2.Table 2
Simulation parameters.
Parameter
Value
Field dimensions
(100×100) m2
R
s
10 m
MaxRt
35 m
Levels of transmission ranges (8 levels)
0,5
,
10,15
,
…
,
35
genmax
200
Amp
100 pJ/bit/m2
E
s
5 nJ/bit
E
rx
5 nJ/bit
E
tx
50 nJ/bit
E
init
2 J
Population size
100
Mutation  probability
0.2
Crossover probability
0.9


## 6.2. Results

We consider the following metrics for evaluation and compare the TASCC algorithm with the OGDC [14], CCP [15], LAEEC [17], and ECCA [18]:(1)
coverage rate of the network;(2)
connectivity of the network;(3)
number of active sensors;(4)
balanced energy consumption;(5)
network lifetime.Experiment 1.
In this experiment, 100 sensor nodes are deployed in the region and the coverage rate of the network is evaluated. A grid is said to be covered, if the center of that grid is covered at least by a sensor node. The coverage rate of the monitoring region versus the number of active sensors at different generations is shown in Figure5. As can be seen in this figure, there is a trade-off between the coverage rate and the number of active sensors. The coverage rate is significantly increased as the number of active sensors increases. At 200th generation, better coverage rate can be obtained with less number of active sensors compared to the other generations. For example, the required active sensors to obtain the coverage rate of 0.9 at generations 50, 100, and 200 are about 50, 40, and 28, respectively.
Figure6 plots the coverage rate versus the number of active sensors for different algorithms. As shown in this figure, with the same number of active sensors, TASCC can obtain a higher coverage rate than other algorithms because TASCC considers the number of active sensors and the coverage rate simultaneously. The coverage rate of CCP decreases with increase in the number of working sensors. This is because a large number of message exchanges are required in CCP to maintain neighborhood information. In the case of low density of active sensors, OGDC provides less coverage rate rather than the other protocols. This is due to the fact that OGDC suffers from many redundant active sensors.Figure 5
The coverage rate versus the number of active sensors at various generations.Figure 6
The coverage rate versus the number of active sensors for different algorithms.Experiment 2.
In this experiment, we consider different number of deployed nodes and the coverage rate of 0.9 and measure the required number of active nodes for satisfying this coverage rate for different algorithms. The results of this experiment are presented in Figure7. According to the results shown in this figure, it can be seen that TASCC has the minimum number of active nodes as compared to the other protocols. With the increasing of number of deployed sensors, TASCC maintains the same number of active sensors (about 25 sensors). This is because the number of required active sensors is independent of the density of the deployed sensors while for other algorithms, the number of required active nodes increases as the number of deployed sensors increases.Figure 7
The number of active sensors versus the number of deployed sensors.Experiment 3.
In this experiment, we consider different number of deployed nodes and the coverage rate of 0.9 and compare the lifetime of the proposed algorithm with other algorithms. The network lifetime is defined as the round when the first node depletes its energy. The changes in the network lifetime are shown in Figure8 where the number of sensors changes from 50 to 200. It can be seen that for all algorithms, as the network size increases, the network lifetime increases too. It is observed that the proposed algorithm has the longest lifetime. This is because in the proposed algorithm, in addition to density control of active nodes, balancing the energy consumption in the network and adjusting the transmission range of nodes result in extending the network lifetime. As mentioned earlier, in other algorithms, the transmission range should be at least twice the size of the sensing range and this may cause more energy consumption and shortening of the network lifetime. The network lifetime in CCP is much shorter than in other algorithms. This is because CCP periodically broadcasts hello messages, and thus more energy will be consumed.Figure 8
Network lifetime versus the number of deployed sensors.Experiment 4.
In this experiment, 200 sensor nodes are deployed in the region and the residual energy of these nodes is measured after 200 generations in order to calculate the unbalanced energy consumption of different algorithms according to (13). The value of this parameter varies between 0 and 1. At the ideal case, the maximum and the minimum residual energy of the nodes will be the same and the value of the unbalanced energy consumption parameter will be 0. On the other hand, in the worst case, the energy of at least one sensor will be depleted while some other nodes are full of energy and according to (13), the value of this parameter will be 1. Figure 9 shows the unbalanced energy consumptions for different algorithms. Based on the results, we find that the unbalanced energy consumption in the proposed algorithm is lower than the other algorithms. This is due to the fact that the proposed algorithm, unlike the other algorithms, considers the balanced energy consumption as an objective and avoids the rapid depletion of the energy and periodically changes the active sensors to balance the residual energy of nodes.Figure 9
Unbalanced energy consumption for different algorithms.Experiment 5.
In this experiment, different network sizes are considered and the number of unconnected sensors in the proposed algorithm is calculated and compared with other algorithms. Figure10 shows the result of this experiment. As shown in this figure, TASCC outperforms other algorithms in terms of connectivity. This is because the proposed algorithm unlike the other algorithms can dynamically adjust the transmission range of the sensors to maintain the connectivity and reduce the unconnected sensors.Figure 10
The number of unconnected sensors versus the network size.


## 7. Conclusions

Maximizing covered area, balancing energy consumption, minimizing the transmission range of nodes, minimizing the number of active nodes, and maintaining the connectivity of nodes are critical issues in WSNs. These issues are usually conflicting. In this paper, we proposed a multiobjective optimization algorithm called TASCC to optimize these conflicting issues simultaneously. We executed different simulation experiments to show the performance of the proposed algorithm. The results obtained from the simulations showed that with the same number of active sensors, TASCC can obtain a higher coverage rate than other algorithms. Moreover, due to balanced energy consumption and dynamically adjusting the transmission range of the sensors in TASCC, the network lifetime was prolonged.



---

*Source: 363815-2015-02-12.xml*