A PSO based Energy Efficient Coverage Control Algorithm for Wireless Sensor Networks

Jin Wang , Chunwei Ju, Yu Gao, Arun Kumar Sangaiah and Gwang-jun Kim

Abstract: Wireless Sensor Networks (WSNs) are large-scale and high-density networks that typically have coverage area overlap. In addition, a random deployment of sensor nodes cannot fully guarantee coverage of the sensing area, which leads to coverage holes in WSNs. Thus, coverage control plays an important role in WSNs. To alleviate unnecessary energy wastage and improve network performance, we consider both energy efficiency and coverage rate for WSNs. In this paper, we present a novel coverage control algorithm based on Particle Swarm Optimization (PSO). Firstly, the sensor nodes are randomly deployed in a target area and remain static after deployment. Then, the whole network is partitioned into grids, and we calculate each grid’s coverage rate and energy consumption. Finally, each sensor nodes’ sensing radius is adjusted according to the coverage rate and energy consumption of each grid. Simulation results show that our algorithm can effectively improve coverage rate and reduce energy consumption.

Keywords: Particle swarm optimization, coverage control, energy efficiency, wireless sensor networks.

1 Introduction

Wireless sensor networks (WSNs) have received significant research attention in recent years, due to their characteristic of low cost and highly adaptive nature [Akyildiz, Su,Sankarasubramaniam et al. (2016)]. WSNs can be adapted for numerous applications,such as target tracking, disaster warning, and wearable devices [Milenkovi, Otto and Jovanov (2006)], etc. We can foresee that a WSN has broad application prospects in the future, which can greatly impact lives. Meanwhile, there are still numerous research aspects remaining to be explored in WSN applications, including localization, data aggregation, data transmission and energy efficiency [Wang (2017); Yang (2018); Singh(2018); Soni (2018)].

Considering network construction issues, coverage control is one of the research efforts in WSNs, it involves sensor deployment [Mo, Li and Vasilakos (2013)] and node scheduling algorithms [Mini, Udgata and Sabat (2014)]. Sensor node deployment approaches play an important role in a WSN that influences its network topology and energy consumption. Also, sensing radius and the sensors communication range are closely relevant with network performance.

Sensor deployment can be classified into two categories: random deployment and planned deployment [Deif and Gadallah (2014)]. For large scale WSNs, random deployment is a feasible scheme. However, this deployment cannot ensure that sensor nodes are deployed evenly giving rise to coverage overlap or coverage holes. Also,network lifetime is a vital part in WSNs. Thus, an efficient coverage deployment algorithm is required in this situation [Al-Karaki (2017); Khalifa (2017)].

With the aim of improving network performance for WSNs, coverage control requires guaranteeing the reliability of the network in the target area [Tirkolaee, Hosseinabadi,Soltani et al. (2018)]. Generally, sensor nodes cannot be evenly deployed in target area due to terrain changes, which can give rise to coverage holes or coverage overlap.Adapting the sensing radius schedule can be a viable solution to eliminate this problem[Jia (2016); Wang (2017)]. Swarm intelligence algorithms have also shown to be an effective approach to enhance network performance [Liu (2012)]. In this work, we adopt Particle Swarm Optimization (PSO) [Kennedy and Eberhart (1995)] to adjust sensing radius, essentially sensor nodes narrow their sensing radius in a dense area and extend their sensing radius in a sparse area.

In this paper, we propose an energy efficient coverage control algorithm based on PSO for WSNs. Firstly, sensor nodes are randomly deployed in a target area and remain static after deployment. Then, the whole network is partitioned into grids, and we calculate each grid’s coverage rate and energy consumption. Finally, we adjust sensing radius of each grid according to its coverage rate and energy consumption.

The remainder of this paper is organized as follows. Section 2 presents some related work.Section 3 presents the system model which includes a network and energy model. Section 4 provides our algorithm in detail. Performance evaluation is shown in Section 5. Section 6 gives some discussion and Section 7 concludes this paper.

2 Related work

Tremendous research efforts have been put on coverage control approaches. Generally,sensing radius of sensor nodes is static, researchers concentrate on topology control for network coverage and energy efficiency. Some of the existing works conducted by researchers are viewed below.

Mini et al. [Mini, Udgata and Sabat (2014)] discussed node deployment and schedule problems in WSNs with the aim of deploying sensor nodes effectively. Artificial Bee Colony (ABC) and PSO algorithms are utilized for deployment. Meanwhile, a weightbased method for sensor nodes scheduling was discussed. It was shown that the ABC-based method gave the best performance. Ab et al. [Ab, Nor, Mohemmed et al. (2009)]presented a PSO and Voronoi diagram-based area coverage optimization algorithm.Differing from PSO-Grid based algorithms, this algorithm utilized the Voronoi diagram to calculate the coverage rate for each candidate solution. This algorithm showed improved performance since the calculation complexity was controlled by only one parameter. However, this deterministically deployment is not suitable for large-scale WSNs.An ant colony-based node scheduling algorithm was presented by Lee and Lee [Lee and Lee (2012)] with the aim of solving energy efficiency problems. The work utilized the Ant Colony Optimization (ACO) algorithm as well as a probability sensor detection model to eliminate this problem. This approach allowing for a more realistic simulation compared with other algorithms. However, complexity of this algorithm is relatively high.Lu et al. [Lu, Li and Pan (2015)] concentrated their work on coverage control and data collection in WSNs. They proposed two approximation algorithms for different cases,and then scheduled their sensor nodes for target coverage and data transmission.Furthermore, they analyzed the network performance of their proposed algorithm.

Energy consumption for coverage control was considered by Wang et al. [Wang, Han,Wu et al. (2013)] where energy consumption and coverage control in mobile WSNs and sensing range were considered differently. By adjusting the sensor sensing range, the network could achieve full coverage under different circumstances. Also, energy consumption was decreased using a delay tolerant scheme. Thus, a balance was achieved a between the energy consumption and the coverage rate. Guo et al. [Guo and Jafarkhani(2016)] conducted research on node deployment in WSNs and presented a model of sensor deployment in the scenario of limited communication range. Two algorithms were presented to optimize node deployment for WSNs.

Pananjady et al. [Pananjady, Bagaria and Vaze (2017)] considered energy efficiency to maximize coverage lifetime and presented an optimal approximation of network lifetime to evaluate network performance. Han et al. [Han, Sun, Xiao et al. (2016)] proposed an energy efficiency scheduling scheme for 3D directional sensor networks. Interestingly,node deployment and scheduling were considered. Mahboubi et al. [Mahboubi, Moezzi,Aghdam et al. (2014)] utilized Voronoi polygons to find coverage holes and then patch the network coverage holes. Both novel edge-based and vertex-based strategies were introduced with simulation results showing the effectiveness of proposed algorithms.

Chang et al. [Chang, Chang, Zhao et al. (2016)] presented an adaptive approach to sensing radius in order to achieve a balance between energy efficiency and network coverage. The sensing radius was adjusted to improve the coverage rate, and a Weighted Voronoi Diagram (WVD) is proposed for energy efficiency. While considering current research blindness in probabilistic area coverage, Yang et al. [Yang, He, Li et al. (2015)]conducted a study on coverage of a full continuous area. Meanwhile, an area coverage optimization algorithm was presented to prolong network lifetime with improved performance justified by simulation.

Ozturk et al. [Ozturk, Karaboga and Gorkemli (2011)] utilized the ABC algorithm for dynamic deployment as well as mobile sensors to improve coverage rate of WSNs. A probabilistic detection model was adapted for simulating the target area and the proposed algorithm was compared with PSO algorithms. Akbarzadeh et al. [Akbarzadeh, Gagne,Parizeau et al. (2013)] presented a probabilistic sensor model to optimize node deployment. They combined it with line-of-sight-based coverage for sensor nodes.Sensing range and sensing angle were considered in their model, and then different optimization schemes were utilized for sensor placement.

Derdour et al. [Derdour, Kechar and Khelfi (2016)] used mobile data collectors to balance energy efficiency and data latency for delay tolerant WSNs. Wang et al. [Wang,Cao, Li et al. (2017)] introduced swarm intelligence into cluster algorithms. ACO was utilized to plan a path for mobile sensors. Wang et al. [Wang, Yin, Zhang et al. (2013)]introduced multiple mobile sinks into a data collection algorithm. Wang et al. [Wang,Cao, Li et al. (2015)] utilized a mobile sink for data collection and cluster sensor-based network using PSO to effectively reduce energy consumption of sensors in a WSN. With the aim of estimating a user’s location, an efficient sensor deployment strategy was presented in Lee and Shin [Lee and Shin (2017)]. Coverage and connectivity were considered therein.

3 System model

3.1 Network model

In this paper, we consider thatmsensor nodes are randomly deployed in aK×Ksquare area, as shown in Fig. 1. Sensor nodes are denoted as {n1, n2, n3, …, nn} respectively.We consider that all sensor nodes remain static after deployment. The whole network is partitioned into a grid. We make the following assumptions:

·All sensors have the same initial energy.

·The sensing radius of each sensor is adjustable.

·There are no significant obstacles in the network.

·The coordinates of the nodes are known.

·We only consider energy consumption in the sensing process.

Figure 1: Network model

3.2 Energy model

We adopt an energy consumption model previously presented [Jia, Chen, Chang et al.(2009)], and we only consider the energy consumption in sensing data process.Considering the sensing radius of a node, a free space (d2 power loss) or multipath fading(d4 power loss) channel model will be used. Sensing energy consumption of a single sensor nodeican be calculated as:

whereeiis the energy consumption of nodei, in a round,ufsandufsrepresent free space and multipath fading model respectively, andriis the sensing radius of sensor nodei. The energy consumption of total sensors in a target area can be calculated as:

The energy consumption per areaEarea, is

whereSis the sensing area. In this paper, we divide the whole network into 5× 5grids,and thusS=K225. There are some other popularly used energy models like first order radio model in [Mo, Li and Vasilakos (2013)].

3.3 Coverage rate calculation

There aremsensor nodes deployed randomly in the network which can be viewed as a node set G =, wherenidenotes nodei. The coordinate of nodeiisand its sensing radius isri.

If pointP(xp,yp)is within sensing radius of nodeni, we assume that it is covered by nodeni. The sensing ratep(ni,P)for pixelPcovered bynias:

The distance between pixelPand nodeniisd(ni,P)=. Since pixelPcan be covered by several nodes at the same time, we consider whether pixelPis covered by nodes setG:

Finally, we can calculate coverage rate of target area as:

wherejandkdenote the length and width of target area.

3.4 Fitness function

In order to minimize energy consumption for the sensor nodes in each sensing step, we adopt area energy consumption as our fitness functionf(x):

4 Our proposed algorithm

4.1 Conventional PSO algorithm

Particle Swarm Optimization (PSO) [Kennedy and Eberhart (1995)] is a swarm intelligence optimization algorithm, which is inspired by behavior of birds in nature.These birds can be abstracted into particles, and each particle will calculate its own fitness value through the fitness function. The particle records its individual optimal solution, and also knows the global optimal solution. Optimal solution can be found through constantly approaching individual optimal solution and global optimal solution.

The PSO algorithm can be described that inNdimensions space, particle setX= (X1,X2,… ,XM)which consists ofMparticles, where the position of particleXiis(Xi1,Xi2,… ,XiN)and its velocity isVi= (Vi1,Vi2,… ,ViN). Particles will dynamically update their speed and position dynamically according to formula (8) and (9).

wherec1andc2are acceleration factor,c1=c2=2.r1andr2are random numbers within[0,1].Xid(t)andVid(t)is position and velocity of particleXiin iterationt.dis number of the spatial dimension.Vmaxis particles’ searching threshold.Ridis individual optimal solution of particle,Rgdis global optimal solution.ωis inertia weight and it can be calculated as formula below.

wheretis round of interaction andtmaxis maximum number of iterations.

4.2 Initial phase

In the initial phase, considermsensor nodes are randomly deployed in the target area and they remain static after deployment. The sensing radiusriof each sensor is initially set the same.

4.3 Grid partition

In this phase, the whole sensor network is partitioned into 25 same sized grids, as shown in Fig. 1. During this step, each sensor nodes’ sensing radiusriin the same grid is equal.But, if sensor nodes are in different grids, their sensing radius can be different. For those grids whose coverage rate is less than 90%, the sensor nodes in these grids can extend their sensing radiusri. Meanwhile, for those grids whose coverage rate is more than 90%,sensor nodes in these grids can narrow their sensing radiusri, as is shown in Fig. 2.

Figure 2: Flow chart of sensing radius adjustment

4.4 Radius adjustment

After the coverage rate of each grid is calculated, the sensing radius of each sensor node can be adjusted. We use PSO to adjust the sensing radiusrof different grids. The number of sensor nodes in a grid ism. We adjust sensing radius of each grid one by one as shown in Fig. 3.

The adjustment approach is shown as below.

Step 1: We initializekparticlesX= (X1,X2,… ,Xk), search interval ofXi(i= 1,2,3,… ,m)is within the coordinate of current grid. Generate a current position and speed for each particle. Initialize individual optimal solution for particleXiisRidand global optimal solution isRgdusing fitness functionf(x)presented in formula (7).

Step 2: If the coverage rate of the grid is less than 90%, then we extend the sensing radiusr; else narrow radiusr, go to Step 6.

Step 3: Upgrade each particle’s position and speed.

Step 4: For each particle, calculate the coverage rate of grid and calculate the fitness functionf(x).

Step 5: Compare individual optimal solution with global optimal solution. If it is smaller,update global optimal solution; else, go to Step 6.

Step 6: Update particles’ position and speed. If particle’s individual optimal solution and global optimal solution become stable, then output the position of particles; else, go to Step 2.

Finally, we can ensure that each grid can get high coverage rate and low energy consumption per area. Thus, we can get balance between coverage rate and energy consumption in WSNs.

Figure 3: Flow chart of our algorithm

5 Performance evaluation

To evaluate the performance of our proposed Sensing Radius Adaptive Coverage Control algorithm (SRACC), we compare it with the previously presented PSO based coverage algorithm and the PSO-VD algorithm [Ab, Nor, Mohemmed et al. (2009)]. All sensor nodes are randomly distributed and the performance is tested under various network topologies. And simulation is conducted in Matlab. The results are evaluated using simulation with parameters given in Tab. 1.

Table 1: Simulation parameters

Improving network performance plays a vital role in coverage control. We first evaluate the coverage rate of our algorithm SRACC compared to PSO-VD [Ab, Nor, Mohemmed et al. (2009)]. As shown in Fig. 4, as the number of sensor nodes is increased the coverage rate improves for both algorithms, however, SRACC has the best performance.As the number of sensor nodes increases over 45, the coverage rate grows slow.

Figure 4: Comparison of coverage rate

Energy consumption is an important aspect for WSNs, since their applications are usually energy constrained. The energy consumption results for the case of 45 sensor nodes are presented in Fig. 5. The PSO algorithm consumes significantly more energy than other two algorithms because it cannot adjust the sensing radius, thus PSO costs more energy in each sensing step. The performance of our algorithm is better than the other algorithms because nodes can reduce their sensing radius in dense regions while maintaining connectivity. The energy consumption significantly increases after the 400 rounds because in node sparse area, sensor nodes have to extend sensing radius at the cost of more energy.

Figure 5: Comparison of energy consumption

Fig. 6 shows average sensing radius performance under different interactions, wheretis round of interaction. From Fig. 6, it can be seen that average sensing range decreases with the growth of interaction. Also, with the growth of interaction, PSO algorithm performs much better in our algorithm. In addition, the sensing radius decreases with sensor number grows. This can effectively restrict the sensing radius since it is relevant to energy consumption. When the number of sensor nodes reduces to 60, the average sensing range of all of the sensors is very close because that density of sensors is high enough so that the sensors do not need a long sensing range.

Figure 6: Average sensing radius of nodes

6 Discussion

Node deployment methods can be divided into two categories: Random deployment and planned deployment. In the random deployment approach, sensor nodes are randomly deployed across the target area. This approach is simple and can be adapted in large scale WSNs. In this circumstance, sensor nodes can be scheduled to avoid coverage redundancy. Sensor nodes can enter sleep mode to save energy and wake up on certain events. Generally, the topology of this approach is fixed does not consider obstacles in the WSN.

For the planned deployment approach, sensor nodes can be deployed in predefined position, i.e. the working environment of the sensor nodes can be considered before being deployed. The energy efficiency of WSNs is also a necessary factor to consider when designing the network topology. This approach requires a significant effort in network construction which is not always suitable for large scale WSN deployments. However, it can ensure coverage rate and energy efficiency for WSNs and it still remains to be explored in further research.

Network lifetime plays a vital role in sensor scheduling algorithms. Since sensor positions may be planned in the previous steps, these nodes can be further scheduled.With the aim of saving energy, some sensors can switch to sleep mode and turn to operating mode in some cases. This rotating work can effectively prolong network lifetime. Also, sensor mobility and sensing range are required to be considered in scheduling schemes.

In our proposed algorithm, we design a sensing radius adjustable approach for static WSNs. This is a feasible way for network coverage, but there are still many aspects need to be considered in further research. For this grid structure, target area may not be suitable for uniform partition, because of obstacle or non-deployable place in network.Also, the effectiveness of the algorithm when some sensor nodes die remains to be discussed. Meanwhile, network scale requires to be expanded in our further research.

7 Conclusion

In this paper, we propose an energy efficient coverage control algorithm for WSNs based on Particle Swarm Optimization (PSO). With the aim of obtaining a balance between coverage rate and energy cost, we adjust the sensing radius of each sensor node to achieve this goal. We first deploy sensor nodes randomly in sensing area, and then we partition the network into grids. Also, the coverage rate and energy consumption of each grid are calculated. Finally, we adopt particle swarm optimization to adjust sensor nodes’sensing radius in different grids. Simulation results show that our proposed algorithm performs better than other PSO algorithms presented in the literature.

Acknowledgments:This research work was supported by the National Natural Science Foundation of China (61772454, 61811530332). Professor Gwang-jun Kim is the corresponding author.