Kalaipriyan Thirugnansambandam,Debnath Bhattacharyya,Jaroslav Frnda,Dinesh Kumar Anguraj and Jan Nedoma

1School of Computer Science and Engineering,VIT University,Chennai Campus,Tamilnadu,India

2Department of Computer Science and Engineering,Koneru Lakshmaiah Education Foundation,Vaddeswaram,Guntur,India

3Department of Quantitative Methods and Economic Informatics,Faculty of Operation and Economics of Transport and Communications,University of Zilina,010 26 Zilina,Slovakia

4Department of Telecommunications,Faculty of Electrical Engineering and Computer Science,VSB-Technical University of Ostrava,708 33 Ostrava-Poruba,Czech Republic

Abstract:In Wireless Sensor Network(WSN),coverage and connectivity are the vital challenges in the target-based region.The linear objective is to find the positions to cover the complete target nodes and connectivity between each sensor for data forwarding towards the base station given a grid with target points and a potential sensor placement position.In this paper,a multiobjective problem on target-based WSN(t-WSN)is derived,which minimizes the number of deployed nodes, and maximizes the cost of coverage and sensing range.An Evolutionary-based Non-Dominated Sorting Genetic Algorithm-II(NSGA-II) is incorporated to tackle this multiobjective problem efficiently.Multiobjective problems are intended to solve different objectives of a problem simultaneously.Bio-inspired algorithms address the NP-hard problem most effectively in recent years.In NSGA-II, the Non-Dominated sorting preserves the better solution in different objectives simultaneously using dominance relation.In the diversity maintenance phase, density estimation and crowd comparison are the two components that balance the exploration and exploitation phase of the algorithm.Performance of NSGA-II on this multiobjective problem is evaluated in terms of performance indicators Overall Non-dominated Vector Generation (ONGV) and Spacing (SP).The simulation results show the proposed method performs outperforms the existing algorithms in different aspects of the model.

Keywords: Focused wireless sensor network; m–coverage k-connectivity problem; non-dominated sorting; NSGA-II

1 Introduction

Wireless Sensor Networks (WSN) is one among the predominant domain where ‘n’number of problems grasps the researchers for achieving reliability, accuracy, the efficiency of the network.This contribution exponentially increased when the applications of WSN are expanded in the environments such as health care, disaster tracking system, military-based applications, etc.In recent years a significant number of optimization problems are solved using nature inspired algorithms [1].IoT based Pay-AsYou-Go Smart Parking System is proposed which uses the unused garbage spaces [2].Another recent model, which uses digital contact tracing to handle the epidemic situations like Covid-19 using IoT [3].In WSN, the sensor nodes are used to sense the data surrounds it and report it to the base station either using a single hop or multi-hop communication process.Sensor node deployment is of two different types, namely ad-hoc and pre-determined manner [4].The ad-hoc type deployment plays a significant role in regions like a deep forest, aquatic nature, etc.Usage of ad-hoc in such regions requires many sensor nodes for effective coverage of the respective region and proper connectivity between deployed sensor nodes.Manual deployment (pre-determined) of sensor nodes is easy to access and requires fewer sensors.However, coverage and connectivity issues are common in both types since the node’s transmission range is less than its restricted power source.The use of wireless connection gets disrupted due to bad weather, etc.Thus, covering targets and maintaining connectivity between sensors that enhance the network lifetime has been considered one of the significant aspects of WSN.

This paper addressesk-coveragem-connected augmented node deployment model in WSN as a multiobjective problem where Non-dominated sorting Genetic Algorithm-II is used to optimize it.The problem is described in this section.Givenktarget regions andPavailable positions for node deployment, the objective is to coverktargets usingmsensor nodes wherem⊆P.As it is given in Fig.1, LetT={λ1,λ2,...,λ10} be the available target regions to be sensed usingS={s1,s2,...,sm} deployed nodes.As per Fig.1 number of sensor nodes inSis six out of 10 available positions ofP.Targetλ2is covered by a Deployed sensors1since the target is within the sensing range of the deployed sensors2which is deployed in the available positionp2and the deployed node can transfer the data to a base station through the available positionsp3andp4.By allocating the sensor nodes concerning its coverage and connectivity range, the minimum objective number of deployed nodes to cover all targets are efficiently achieved.This problem is considered an NP-complete problem [5].Achieving optimization in this problem is highly preferable since exact methods take more high time complexity when compared to the optimization approach.

Figure 1:Two-covered one-connected network

2 Related Work

In the past few decades, research contributions on optimizing WSN problems using heuristic and metaheuristics are higher than earlier research exposure [5–9].In this literature, coverage and connectivity related algorithms are described with their predominant features.

A detailed Survey has been recorded on different methods for effective node placement in WSN by [10].In [5] a contradictory set of objectives are taken for effective node placement in WSN, namely energy cost, sensible area, and network reliability.The flaws in their approach are the inadequate coverage of complete targets in the given region.The use of meta-heuristics failed to achieve this particular issue which made the algorithm an ineffective one.A new approach for solving the WSN issue is dividing a region into a disjoint sub-region and imposed active and passive mode of operations in it by [11].The proposed methodology of Cardie was later redefined in [5] to enhance the lifetime of the network by imposing redundant nodes.Irrespective of coverage and connectivity, this approach achieves better results along with improved disjoint sets.

Research on the optimization of resource allocation algorithm in WSN is discussed by [12].The lifetime of network and connectivity are the objectives considered in this paper, which takes the sensor positions and transmission power level as their attributes to solve the problem.MOEA/D is used to solve the given problem to achieve the objectives with fewer deployed sensor nodes.Coverage was not handled in this paper.Author Harizan et al.[13] proposed an NSGA-II with modified dominance has been proposed for the scheduling problem.The multiple parameters as coverage, connectivity and residual energy of the sensor nodes are considered.A probabilistic sensing model (PSM) and harmony search algorithm (HSA) approach are used in the same type of problem in WSN to achieve the balance between the network coverage performance and the network cost [14].

In 2012, a multi coverage based WSN problem is handled in [15], three different coverage,namely simple coverage,kandQcoverage.For the optimization process, an exhaustive cover set defining process is used in this approach.For the inclusion of connectivity in the proposed algorithm, an M-connected approach is included for optimization.The algorithm’s time complexity is higher since the algorithm flow included each node one by one and check for all possible combinations in the set for adaptive placement of nodes.

A simulation-based approach for effective node placement is proposed by [16], where several available positions to place the sensor nodes are given.Without colliding the connectivity between sensor nodes, the nodes should be placed with the minimal number—another approach based on GA proposed in [17] as relay sensor node placement algorithm.This paper’s defined objective is to efficiently place the nodes in the given positions, thus minimizing the number of sensors without colliding its connectivity between relay nodes.Using GA, another approach for attacking coverage problem in WSN is proposed to enhance its lifetime.In this approach, sensing targets are not used for simulation.Only the sensors nodes are placed to cover the simulation region without any targets in it.In our proposed method, this problem is addressed.Another GA based approach for addressing the same issue as our proposed method has been made in [4].However, this method reproduces offspring so that it becomes invalid, and a solution repair process is needed here.In our proposed algorithm, a multiobjective optimization algorithm NSGA-II is used to address this issue and Pareto set solutions.

3 Multiobjective Optimization

This section comprises the prescribed definition of the multiobjective optimization problem [18] and Pareto dominance operators, which helps to understand the proposed work better.

Figure 2:Dominance relation

4 Problem Formulation

In this section the the formulation oft-WSN problem is defined with an example along with the objectives.

4.1 Network Model

Let us assume that the simulation region for target-based WSN is of the two-dimensional region.Our model positions the positions to deploy the sensor nodes randomly based on the available targets.The target points and sensor nodes are static for some available positions.In our proposed model, the available position to sense targets are given with a different range, as shown in Tab.1.Similarly, communication between nodes are given as coverage range which is listed in same Tab.1.

4.2 Problem Definition

Let us define the notations that are used to create the system model.

1.Set of Target pointsT={λ1,λ2,...,λk}

2.Set of available positions of sensor nodes to cover targetsP={ρ1,ρ2,...,ρh}

3.Set of deployed sensor nodes in available positions S={s1,s2,...,sm|d≤m}

4.Rcommrepresents sensor node communication range.

5.Rsenrepresents sensor node sensing range.

6.drepresents the distance between the target pointλito Deployed Sensor sj

7.Cov(λi)denotes the sensor nodes that cover the target pointsλi.This can be represented as:

8.Tcov(si)denotes the target points that are covered by si.This can be represented as:

9.Comm(si)denotes the sensor nodes that are covered by sj.This can be represented as:

Boolean representation is used to define whether the targetiis covered by nodej.Points 7–9 is represented as follows:

4.3 Objectives

There are three objectives of coverage, and connected problem are considered in this paper.The objectives are defined as follows:

1.Minimize the number of Deployed Nodes:The first objective is defined to minimize the number of deployed sensor nodes from the available positionsh.It can be formulated as

2.Maximize the cost of coverage:It can be represented as:

whereCostCov=andk∈TandCov(λi)⊆S

3.Maximize the cost of connection:Mathematical representation can be stated as:

whereCostCov=andm∈S andCov(λi)⊆T.

5 Non-Dominated Sorting Genetic Algorithm II on Coverage-Connected Problem

This section holds a four-folded algorithm for optimizing coverage-connected problem using NSGA II [19].In this section, a discussion on the Non-dominated sorting method followed by preservation of diversity will be explained in the second fold, and reproduction operators are discussed.In the final fold, a complete algorithm for solving the coverage-connected problem using NSGA-II is described.NSGA-II is chosen to solvem-connectedk-coverge problem over other multiobjective optimization techniques due to its following advantages.The advantages are listed as follows:Non-Dominated sorting techniques are utilized to enhance the solution search towards pareto-optimal solutions.The use of crowding distance improvises the diversity of search.The usage of Elitist technique preserves the optimal solution in every iteration [20].

5.1 Non-Dominated Sorting and Density Estimation

Non-dominated sorting is the process of sorting the individuals based on its domination set.It is a rank-based selection method to accentuate the Pareto front individuals to improve the algorithm’s search capability.A detailed description of Non-Dominated sorting is given in Algorithm 1.This algorithm is considered as a function to be called by NSGA-II in Algorithm 3.

I looked at her quizzically. What do you mean? Of course you put them out. They were sitting on the porch in a paper bag, right where you said they d be.

5.2 Preserving Diversity

A multiobjective evolutionary algorithm is supposed to hold two properties such as:

• Convergence towards Pareto front individuals.

• A diversified search should be done during the run.

In NSGA-II, two methods are used to handle this diversity preservation:density estimation and crowded comparison operator.This method eliminates the process of user-dependent feature.

Density estimation denotes the dense population around an individuali∈Υi.It is represented as Υi(dk)for individuali.Whenmis represented as objectives, thenfm(i)represents the fitness of individualiwith respective to objectivemthenrepresents the maximum value of objective functionmfrom the entire populationtandrepresents the minimum value.Algorithm 2 represents the crowding distance function.

5.3 Crowd Comparison(≺n)

For selecting an individual, the crowding comparison operator can be used in the crowded population.Crowd comparison operator is used when both the individual obtains the same rank in non-dominated sorting.Each individualC∈Pconsists of attributes, namely 1.Non-dominated Ranking (Crank) and crowd distance (Cd).C1≺n C2if it falls in two conditions which are:

when an individual fall into these two conditions, then the individual with a lower rank will be selected.

Algorithm 1:Non_Dominated_Sort(χ)Input:χ 1:for each solution uϵχ do 2:Du ←∅ /* Solutions dominated by u 3:Nu ←0 /* # solutions that dominate u 4:for each solution vϵχ do 5:if (u ≺v) then 6:Du ←Du ∪{u} /* Adds individual u to non-dominant set */7:else if (v ≺u) then 8:Nu ←Nu+1 /* Increase domination count for individual u */9:end if 10:end for 11:if (Nu=0) then 12:urank ←1 /* Assigns the non-dominance rank as 1 for individual u */13:ϒ1 ←ϒ1 ∪{u} /* Adds individual u to Pareto Front set */14:end if 15:end for 16: i ←1 17:while ϒiimages/BZ_64_2034_2820_2070_2866.png∅do 18:T ←∅19:for each solution uϵϒi do 20:for each solution vϵDu do 21:Nv ←Nv-1 /* decreases domination count for individual v */22:if Nv=0 then 23:vrank ←i+1 /* Assigns rank for individual v */24:T ←T ∪{v}25:end if 26:end for 27:end for 28:i ←i+1 29:ϒi ←T 30:end while Output:O

Algorithm 2:Crowd_Distance (ϒi)Input:2: j ←|ϒi|3: for k ←1 to j do 4:ϒi(dk)←0 5:for each objective m do 6:ϒi ←sort(ϒi,m) /* Sort the population with respect to all objectives 7:ϒi[1]←∞, ϒi[j]←∞

?

5.4 Process of NSGA-II on m-Connected k-Coverage

The individuals are represented as chromosomes, and a complete solution set can be represented as populationP.Boolean representation is used to represent each individualC.For Reproduction (Offspring), simulated binary crossover and 2-point mutation are used for effective diversification.After initializing the population, the offspring is done with the parent population.Children are produced and appended along with their parents.The detailed flow of NSGA-II is given in Algorithm 3.

Algorithm 3:NSGA-II on m-Connected k-Coverage Input:Termination Criteria (Max_IT), Fitness function (f()), #Chromosomes (N), #Potential Positions (PP)1. begin 2: t ←1 3:Initialize population Pt ←(C1,C2,...Ci,...,CN) where Ci ←{Gi,1,Gi,2,...,Gi,j,...,,Gi,PP|∀Gi,jϵ{0,1}}4: while (t ≤Max_IT) do 5:Ot ←OffSpring (Pt)6:χt ←Pt ∪Ot 7:ϒ ←Non_Dominated_Sort (χt)where ϒ ←{y1,y2,...}∀m 8:Q ←∅and i ←1 9 : for each yiϵϒ do 10:Q ←Q ∪yi 11:end for 12:L ←Crowd_Distance(ϒ) /* Calls density estimator 13:Crowd_Compare_Sort ( L,≺n) /* calls Crowd comparison function 14:Pt+1 ←Q ∪L[1: (N-|Q|)]15:t ←t+1 16: end while 17: end Output:Pareto Front Set

6 Experimental Results&Discussion

The experimental setup for evaluating the proposed algorithm’s performance on thek-coveragem-connected problem, NSGA-II, is implemented on the problem using MATLAB version 8.4 in the system configured with Intel Core i7 processor, 3.4 GHz processor speed, and 4 GB RAM.The designed testbed for this paper’s described problem, two different grid-based scenarios are generated, namely WSN1 with a 300-m × 300-m grid and WSN2 with a 500-m × 500-m grid.The base station for WSN1 and WSN2 were set in the position coordinates of (300, 150) and(500, 250), respectively.The available positions for sensor nodes and targets are randomly placed in the grid.The parameters are given in Tab.1.

Table 1:Parameter setting

6.1 Performance Metrics

Performance measures using for evaluating the proposed algorithm are F-value, Computation time in seconds.F-value:F-value is the ratio between the number of available positions to the number of deployed sensors in it (a higher value is better).It can be formulated as:

Computational Time:Computational time is defined as the algorithm’s time to perform its entire run.In this simulation, the computational time is given in seconds.

The simulation results are tabulated in Tab.2.

6.2 Performance Measures Using Multiobjective Performance Indicators

Figs.3 and 4 are showing the performance of the proposed algorithm in terms of multiobjective solutions, two effective unary indicators are evaluated with Pareto front solutions, namely Overall non-dominated vector generation (ONGV) and Spacing (SP).To evaluate the performance of the proposed algorithm in terms of multiobjective solutions, two effective unary indicators are evaluated with Pareto front solutions, namely Overall non-dominated vector generation(ONGV) [21] and Spacing (SP) [22].ONGC and SP are formulated as follows:

Figure 3:Simulation setup of WSN1 (300 × 300)

Figure 4:Simulation setup of WSN2 (500 × 500)

|γ|cdenotes the number of individuals in the Pareto front and|γ|cfor each objectivef()withmobjectives andis denoted as the mean ofdj.In terms of ONGV higher, the values depict the algorithm’s efficiency in finding Pareto front solutions.SP value depicts a complete solution set efficiency, and when the value is near 0, it obtains a higher performance impact.For evaluating other algorithms in terms of multiobjective performance indicators, their final iteration solutions are considered.The performance measures are shown in Tab.3.

Table 2:Simulated Results of WSN1 and WSN2 network grid with different coverage and sensing range.Best values are depicted in bold

Table 2:Continued

Table 3:Multiobjective performance indicators for WSN1 and WSN2 network grid with different coverage and sensing range.Best values are depicted in bold

Table 3:Continued

6.3 Result Analysis

For comparison purpose, we simulated other existing algorithms, namely heuristic-based method Greedy Method and GA based method [15–17,23] and GA in [1].Tabs.2 and 3 comprises the results in terms of efficiency and Pareto front individuals, respectively.From Tab.2, the results of the proposed algorithm show significant performance in terms of F-value on coverage and connection range (k,m) values (1, 1) and (2, 2).Tab.3 holds the ONGV and SP metric results,which are performance indicators for evaluating the multiobjective problem.Figs.5 and 6 shows the performance comparison of deployed sensor nodes for all algorithm with different coverage and connectivity range and the performance comparison of WSN1 and WSN2.From the given results, it is justified that the proposed algorithm’s performance outperforms with appropriate performance measures.

Figure 5:Comparison of # deployed nodes w.r.t coverage and connectivity range for WSN1

Figure 6:Comparison of # deployed nodes w.r.t coverage and connectivity range for WSN2

7 Conclusion

In this paper, the NSGA-II optimization algorithm is used to handle the multiobjective coverage connectivity problem in WSN.The described objectives were efficiently handled using NSGA-II to obtain a high number of Pareto front set solutions.The proposed NSGA-II on coverage connectivity was tested with different grid size, communication and sensing range.In terms of F-Value, the proposed method performance with superior values for most of the simulations.Also, in terms of computational time, the proposed algorithm outperforms when compared with the existing algorithms.For justifying the proposed algorithm, five existing techniques were simulated with the same grid, and the values were tabulated in terms of F-Value and Computational time.For comparing the results in terms of multiobjective performance indicators, the final iteration individuals are taken to count with respect to its Euclidian distance.

The future directions of the proposed model can be enhanced by solving more number of objectives.On the other hand, improvising heterogeneous algorithms for solvingm-connectedkcoverge problem is also an another scope of the research.

Funding Statement:This research has been funded with the support of the project SP2021/45,assigned to VSB-Technical University of Ostrava, the Ministry of Education, Youth and Sports in the Czech Republic.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.