Mathematical modelling for reducing the sensing of redundant information in WSNs based on biologically inspired techniques

Abstract

Wireless sensor networks (WSNs) found application in many diverse fields, starting from environment monitoring to machine health monitoring. The sensor in WSNs senses information. Sensing and transmitting this information consume most of the energy. Also, this information requires proper processing before final usages. This paper deals with minimising the redundant information sensed by the sensors in WSNs to reduce the unnecessary energy consumption and prolong the network lifetime. The redundant information is expressed in terms of the overlapping sensing area of the working sensors set. A mathematical model is proposed to find the redundant information in terms of the overlapping area. A combined meta-heuristic approach is used to achieve the optimal coverage, and the effect of the overlapping area is considered in the objective function to reduce the amount of redundant information sensed by the working sensors set. Improved genetic algorithm (IGA) and Binary ant colony algorithm (BACA) are used as meta-heuristic tools to optimise the multi-objective function. The objective was to find the minimum number of sensors that cover a complete scenario with minimum overlapping sensing region. The results show that optimal coverage with the minimum working sensor set is achieved and then by incorporating the concept of overlapping area in the objective function, sensing of redundant information is further reduced.

Keywords

Improved genetic algorithm Binary ant colony algorithm Redundant information Objective function Overlapping area

1 Introduction

Random deployment of the wireless sensor in WSNs along with the sensor’s location information has made the localisation issue a critical challenge in WSNs. One of the proficient ways to deal with this type of problem is the meta-heuristic approach based on the simulation [1 –4]. Several meta-heuristic approaches have been proposed in WSNs such as GA, ACO, Lion Optimization (LO), Particle Swarm Optimization (PSO), Support Vector Machines (SVM) Artificial Neural Networks (ANNs) etc. [5 –10]. Along with these intelligent algorithms, and their modified versions are also used to deal with serious issues associated with WSNs [11 –16].

Regardless of the benefits of such meta-heuristic approaches, its major weakness is the sensing of the redundant information and the presence of redundant sensors. Both these factors affect the lifetime of sensors in WSNs drastically. However, the sensors have a limited lifetime due to the limit of cost and volume [17, 18]. Energy to the sensors cannot be supplied once employed or regenerated, so the optimal coverage and the energy consumed by the nodes are the two critical problems in WSNs [2, 19]. In this paper, a novel approach has been proposed to deal with the sensing of redundant information. A mathematical model is proposed to find the redundant information sensed by the sensors using a combined meta-heuristic approach. The contribution of the authors in the paper is summarised as follows.

A very effective combined meta-heuristic approach, IGA-BACA, is applied in WSNs for maximising the network coverage along with reducing the number of sensors required.

A mathematical model is proposed for finding the redundant information sensed by the sensor node having a circular sensing area. Redundant information sensed by active nodes is expressed in terms of the overlapping area.

Designing of a multi-objective function that incorporates the concept of the overlapping area.

In Section 2, the theoretical background and the related work have been presented. In which, the basics of heuristic techniques used has been discussed.

2 Theoretical background and related work

2.1 GA and Adaptive GA(or IGA)

GA is a global meta-heuristic random search technique, proposed in the early seventies by John H. Holland [5]. It follows three operators, namely reproduction, crossover and mutation. It can be considered as a biological evolutionary process in which a population of certain solutions evolves over a series of generations [20]. It retains a set of solutions known as chromosomes, which are obtained through fitness function in every generation. It is then shortlisted for reproduction according to their fitness value. The selection process follows the principle of survival of the fittest. Solutions having good fitness values are selected for reproduction whereas the bad solutions are rejected. The shortlisted solutions go through other two genetic operator crossover and mutation. Now crossover leads to the interchange of genetic-based material between solutions because crossed solutions can produce an individual with either best or worst fitness. It occurs only with some probabilityP_c known as crossover probability or crossover rate. The mutation modifies a solution with probability P_m known as mutation probability. The role of mutation probability is to explore the unexplored genetic material. GA finds a globally optimal solution or nearby solution and hence, reduces the chances of getting the local minimum.

In Adaptive Genetic algorithm (AGA), the crossover and mutation probability changes adaptively according to the different condition of the individuals which prevents the premature convergence [21]. Mathematical expression for P_c and P_m is given in equation 1 and 2. $P_{c} = {\begin{matrix} \frac{k_{1} (f_{\max} - f^{'})}{f_{\max} - f_{avg}} & f^{'} > f_{avg} \\ k_{3} & f^{'} < f_{avg} \end{matrix}$ (1) $P_{m} = {\begin{matrix} \frac{k_{2} (f_{\max} - f)}{f_{\max} - f_{avg}} & f > f_{avg} \\ k_{4} & f < f_{avg} \end{matrix}$ (2)

Where P_c is known as crossover probability, P_m is known as mutation probability, f_max is known as the highest fitness of population, f_avg is known as the average fitness of the population, f′ is known as the higher fitness of two strings used for crossover, f is known as the fitness of the individuals to mutate. The constant k₁, k₂, k₃ and k₄ have to be less than 1, to restrict the value of P_c and P_m to the range [0,1]. Also, k₁ and k₃ are bigger than other two constants.

2.2 Ant Colony Optimisation (ACO) and BACA

ACO is a kind of simulated evolutionary algorithm [22]. The basic concept in ACO is that an ant while searching for food releases a peculiar type of pheromone in its path, which makes other ants perceive a kind of oddity and tends to lean towards the route of higher intensity [20]. ACO evaluates the optimal route through a continuous process of accumulation and update of chemical released by them, pheromones, and it obtains optimised value by undergoing appropriate times of generation. Although ACO finds better solutions, gets good performance on parallel computing and can be easily combined with other algorithms, it still has some shortcomings. The initial stages lack pheromone as a result of which it searches slowly and results in the local optimal solution, i.e. premature convergence [23].

To overcome the above issue, BACA is used. BACA network is illustrated in Fig. 1. The work of ants is divided, and the same routine searches by a different type of ants, and pheromone is left on each edge. As an intelligent individual, each ant selects one edge out of two. The incidence matrix traversed by each kind of ant, needs only (2 × n) ′s space, which, up to some extent, solve the problem of reduction in solution quality. Hence, in the next iteration or experiment, the efficiency of the algorithm increases greatly [23]. The BACA make use of binary coding instead of decimal coding, and the binary coding has a better traversal search capability as compared to decimal coding.

Fig. 1

BACA network.

Define a direct graph, G = (V, R), where the node set V is $\begin{matrix} {{v_{0} (c_{s}), v_{1} ((c_{N}^{0})), v_{2} ((c_{N}^{1})), v_{3} ((c_{N - 1}^{0})), v_{4} ((c_{N - 1}^{1})), . . ., \\ v_{2 N - 3} ((c_{2}^{0}), v_{2 N - 2} ((c_{2}^{1}), v_{2 N - 1} ((c_{1}^{0}), v_{2 N} ((c_{1}^{1})}} \end{matrix}$ (3)

Where c_s is the starting node, $c_{j}^{0}$ and $c_{j}^{1}$ are separately used to represent the value of 0 and 1 of bit b_j in binary-coding. For every node (j = 1, 2, 3, . . . , N), there are only two directed arcs pointing towards $c_{j - 1}^{0}$ and $c_{j - 1}^{1}$ , which respectively stands for the 0 and 1 allowed next states for all the ants and N represents the binary encoding length [24].

In the initial stage, information associated to all path are equal, let it be τ_i,j (0) = C where C is a constant, Δτ_i,j (0) (i, j = 1, 2, . . . , N). During the operation of move, k number of ants determines the direction (where k = 1, 2, . . . , m) according to the info of each path and the probability of movement is define as $\begin{matrix} p_{i, j}^{k} = \frac{(τ_{i, j}^{α} (t) . η_{i, j}^{β} (t))}{(\sum_{s \in allowedk} τ_{i, j}^{α} (t) . η_{i, j}^{β} (t))} \end{matrix}$ (4)

Where $p_{i, j}^{k}$ represent the movement probability, that k ants move from location i to location j, m represent the number of ants, α and β represent the relative importance of moving path and visibility respectively. Both α and β should be greater than or equal to one. τ_i,j is the unused information in the ij connection at t moment. η_i,j represent the visualness in the ij connection. Allowed_k = (0, 1) is the next selected status. As pheromones evaporate as time passage so the leaving information also starts disappearing with passage of time. ρ (0 ≤ ρ ≤ 1) represents the perseverance of a moving path and information loss degree is 1 - ρ. The ant completes one cycle after n moment. The τ_i,j is represented as $\begin{matrix} τ_{i, j} (t + 1) = ρ . τ_{i, j} (t) + Δ τ_{i, j} \end{matrix}$ (5)

Where $Δ τ_{i, j} = \frac{1}{f_{best} (S)}$ ,f_best (S) is the best-iteration cost. Compared with the basic ant colony, the BACA differs only in the path selection of ant. There are only two states 0 and 1 in a binary ant colony; the ant do not need to remember that node that has been travelled, it selects only from the two path pheromones.

2.3 IGA with BACA

BACA finds the solution by taking the initial population from the GA. The initial population is generated randomly, which go through GA evolution. Simultaneously, the result obtained by GA is utilised to initialise the pheromones information of the network. If the last condition of the loop is met, then the algorithm will terminate; otherwise ants will traverse, pheromones update and reserve of optimal solution step is executed. Further, GA operators are operated to obtain a set of solution and retain the optimal solution. And lastly, the optimal updated pheromones are used to decide whether the termination is met or not. A one to one correspondence between IGA-BACA parameters and WSNs is given in Table 1.

Table 1
Analogous parameters in IGA-BACA algorithm and sensor deployment

IGA-BACA Algorithm Sensor deployment problem

Solution of a food source Sensor distribution

N dimensions in each solution N sensor coordinates

Fitness of the solution Coverage rate of interest area

Maximum fitness Optimum sensor deployment

IGA-BACA Algorithm	Sensor deployment problem
Solution of a food source	Sensor distribution
N dimensions in each solution	N sensor coordinates
Fitness of the solution	Coverage rate of interest area
Maximum fitness	Optimum sensor deployment

2.4 WSN nodes optimal coverage based on IGA-BACA

Optimal coverage of WSN node is a multiple objective optimization problem, which can be represented as S = (s₁, s₂, . . . , s_i, . . . , s_N) is the set of existing sensors, the target is to get sensor node set S′, that provides utmost coverage rate with the lowest number of working sensors. If f₁ (S′) represents maximal network coverage and f₂ (S′), minimum working nodes. This conflict undermines them both, multiple objective optimisation models in WSN is changed to maximal objective function f (S′) given by $\begin{matrix} f (S^{'}) = (f_{1} (S^{'}) . f_{1} (S^{'}) / f_{2} (S^{'})) \end{matrix}$ (6) The optimal coverage based on IGA-BACA implementation in WSN is as follows [24].

2.4.1 Code

The completion of mapping from solution space to coding space of optimisation problem is a key problem. The control vector L = (l₁, l₂, . . . , l_i, . . . , l_N) of wireless sensor node for random distribution of working sensor is expressed in form of binary coding, that represent the location of all sensor nodes. Here the value of l_i can be either 0 or 1, which reflects the sleep or active state of the sensor node i. The initialisation of a gene in a chromosome in GA has one to one correlation with selection of nodes.

2.4.2 Initial solution and adaptation function

A total of 8 sensors are randomly distributed over a region, where the sensors (1, 2, 3, 5, 7, 8, 10, 11, 12) are working sensors nodes and the corresponding control vector is {111010110111} which is shown in Fig. 2. Equation 9 is used as adaptation function; the larger the value of the functions, the large will be selection probability of individual.

Fig. 2

Control vector of 9 working sensors out of 12 is {1 1 1 0 1 0 1 1 0 1 1 1}.

2.4.3 Operation operator

It is a combination of GA and ACO operators. A total of four operators namely reproduction, crossover, mutation and lastly update pheromone operator are there in IGA-BACA. In IGA-BACA, the first operator reproduces offspring to the new colony depending on probability in a fraction to their adaptive value. After the first operator, the offspring with better fitness are retained, and inferior offspring are rejected or removed, and hence the average fitness value associated with the colony is increasing, however, in this process, the number of possible varieties is lost. The crossover operator selects a pair of individuals according to probability P_c, and there may be a chance that crossed solutions can either produce ones with better or worse fitness value. The mutation operator modifies a solution or offspring with probability P_m. The role of mutation operator is to explore the unexplored genetic material.

The update pheromone operator (T_g) represent a mapping of update pheromone for optimal offspring selected through ant sequence. By Max-Min rule pheromones will be only released in the optimal ant traverse path, mathematically Δτ (i, j) =1/(f_best (S)), f_best (S) is the best-iteration cost or best global solution. The probability of update pheromone operator is given by $\begin{matrix} P {T_{g} = x_{i}} = \frac{f (x_{i})}{\sum_{k = 1}^{N} f (x_{k})} \end{matrix}$ (7) Where, N is the total number of offspring.

A diagrammatic representation of this section is illustrated in the flow chart in Fig. 8 [24].

The rest of the paper is structured as follows. An expression is derived for calculating the overlapping area in section III. The system model for the proposed approach is illustrated in section IV. The simulation results are discussed in section V. Finally, in section VI, the conclusion and future scope of the work is highlighted.

3 Mathematical formulation for overlapping area

The overlapping area between the circles represents the redundant information, as both the sensor sensing the common information. A mathematical formulation to find the common area has been given below.

Let us assume that in the two circles, one with centre A and other as centre C have the same radius, r, overlapping each other. The distance between the centres, d affects the size of the overlapping area, as shown in Fig. 3. But at first, without going to mathematics, one can observe some of the points. First when d = 0 the overlapping area is πr² and second when d ≥ 2r then the overlapping area is 0 [25].

Fig. 3

Overlapping circles with centres A and C.

The common area is due to the overlapping sectors, as shown in Fig. 4. To find the overlapping area, first the area of the sector for one circle is calculated, then the area due to the segment of the sector is calculated indirectly by eliminating the area of its triangle. Then, it is multiplied by two to obtain the desirable overlapping area, as explained in Fig. 5.

Fig. 4

Overlapping sectors.

Fig. 5

Segment of sector.

The area of the sector of a circle, Area_sector = (θ/2) r², where θ is the central angle in radian, of the sector. △AED is an isosceles triangle with points A (centre of the first circle), E and D (intersection point of the circle) shown in Fig. 6. The height of the isosceles triangle is d/2. To find the central angle of the sector θ, △AED is divided into two right angle triangles of height/2, hypotenuse r and angle between the hypotenuse and height θ/2 as shown in Fig. 7. From Fig. 7, $\begin{matrix} \cos (θ / 2) = (d / 2) / r \Rightarrow \cos (θ / 2) = d / 2 r \end{matrix}$ (8) solving for θ we get, $\begin{matrix} θ / 2 = \cos^{- 1} (d / 2 r) \Rightarrow θ = 2 \cos^{- 1} (d / 2 r) \end{matrix}$ (9) At this particular time, one can conclude that |d|≤2r is a necessary condition for a circle to overlap. Now the area of the sector is given by $\begin{matrix} {Area}_{sector} & = (θ / 2) r^{2} = (2 \cos^{- 1} (d / 2 r)) r^{2} / 2 \\ = r^{2} \cos^{- 1} (d / 2 r) \end{matrix}$ (10) To obtain the area due to the sector’s segment first the area of △ADE needs to be evaluated, which is given by Area_triangle = (1/2) bh, Where base, b is DE and height, h is d/2.

There are two methods to obtain the triangle area. In the first method Pythagoras theorem is used to get an expression for the base of the △AED, b in term of r and d. If b is the base of the △AED then b/2 is the base of the right angle triangles.

By the Pythagoras theorem, we have, $\begin{matrix} (b / 2)^{2} + (d / 2)^{2} = r^{2} \Rightarrow b = \sqrt{4 r^{2} - d^{2}} \end{matrix}$ (11) Hence the area of the triangle is given by $\begin{matrix} {Area}_{triangle} = (1 / 2) bh = (d / 4) \sqrt{4 r^{2} - d^{2}} \end{matrix}$ (12)

In the second method, the triangle area is expressed in terms of r and θ. For this, first b and h is calculated in terms of r and θ. $\begin{matrix} \sin (θ / 2) = (b / 2) / r \Rightarrow b = 2 rsin (θ / 2) \end{matrix}$ (13) $\begin{matrix} \cos (θ / 2) = h / r \Rightarrow h = rcos (θ / 2) \end{matrix}$ (14) Now area of the triangle can be given by $\begin{matrix} {Area}_{triangle} = r^{2} \sin (θ / 2) \cos (θ / 2) \end{matrix}$ (15) Using double-angle formula, sin (2z) =2sinzcosz, the area of the triangle can be reduced to $\begin{matrix} {Area}_{triangle} = (1 / 2) r^{2} \sin (θ) \end{matrix}$ (16) Now area due to the segment is obtained as a difference in the area between the sector and the triangle. Area of the sector’s segment (in terms of r and θ). $\begin{matrix} {Area}_{segment} & = {Area}_{sector} - {Area}_{triangle} \\ \Rightarrow (r^{2} / 2) (θ - \sin θ) \end{matrix}$ (17) Area of the sector’s segment (in terms of r and d). $\begin{matrix} {Area}_{segment} = r^{2} \cos^{- 1} (d / 2 r) - (d / 4) \sqrt{4 r^{2} - d^{2}} \end{matrix}$ (18) Area of the overlapping region in terms of r and θ. $\begin{matrix} {Area}_{overlapping} = 2 {Area}_{segment} = r^{2} (θ - \sin θ) \end{matrix}$ (19) with 0 ≤ θ ≤ 2π. Area of the overlapping region in terms of r and d. $\begin{matrix} {Area}_{overlapping} = 2 {Area}_{segment} = 2 r^{2} \cos^{- 1} \\ (d / 2 r) - (d / 2) \sqrt{4 r^{2} - d^{2}}) \end{matrix}$ (20) with 0 ≤ d ≤ 2r.

4 System model

Network coverage is one of the critical problems in WSNs. The coverage should reach the maximum with a certain level of Quality of Service (QoS) [26 –28]. Maintaining the required amount of QoS is achieved by measuring the WSNs coverage rate to check whether blind areas are present or not. Blind areas are regions which are not sensed by any of the sensors. The density of sensor nodes can be changed based on the requirement by keeping a total number of sensor nodes constant, i.e. one can deploy more sensors in more vital area to increase the reliability. There are two types of deployment viz. random coverage and certainty covering. In random covering sensors, deployment task is random, whereas in certainty covering the sensors deployment task is based upon specific algorithms. In the later certainty covering, if someones want to cover the area using a minimum working set of nodes, then determining the coverage area size is the first task that needs to be done. The certainty covering technique is adopted in this paper. In recent times, the method mentioned in [26] is widely used to find the minimum set of nodes that is enough to cover the given area and turn off the remaining nodes. In WSNs, with increase in the number of sensing nodes, the network cost also increases. The optimal set of nodes is the minimum working set of nodes that will not affect the network coverage.

Let us suppose that the total area to be monitored is A and is a 2D plane. Further, it is divided into mxn grids with each grid having unit area. A total of N sensor nodes are first distributed randomly in the given monitoring area A and sensor nodes set is represented by S = (s₁, s₂, . . . , s_i, . . . , s_N). The sensor node s₁ has a coordinate (x_i, y_i) in the region A, coordinate of each sensor node is known and all sensor node have effective radii of r and s_i = {x_i, y_i, r}. The sensing radius of node s_i is consider to be circular region with centre, (x_i, y_i) and effective radius, r. Let p be any arbitrary point in the region A where p ∈ A, and d is the Euclidean distance then d (p, (x_i, y_i)) ≤ r where i ∈ [1, N].

Each grids are target point (a₁, a₂, . . . , a_j, . . . , a_m×n) and need to be sensed in the region A. Let the target point a_j be in the sensing region of the sensor node s_i then d (a_j, s_i) ≤ r. For the sensor node s_i the communication range is the circle with centre, (x_i, y_i) and radius, r. Now if d (s_i, s_j) ≤ r_c then there will be direct communication possible between the sensor node s_i and s_j.

An undirected communication graph G, consisting of S sensor node is said to be connected if their exit a communicating path between any two sensor node which means d should be d (s_i, s_j) ≤ r_c where S is sensor node set. If any point in the region A is sensed by a sensor node of S, then S is called as the covering set of A, and if the communication graph G is connected then S is called as the connected covering set of A. Let S′ be the minimal subset of S, and if S′ covers the monitoring area completely then one can conclude that communication diagram extracted from S′ is connected. The goal of optimisation should be such that each grid in A should be at least sensed by a sensor. For connectivity to exit the communication range r_c, it should be at least twice as that of sensing radius r, means r_c ≥ 2r. So by maintaining this relation one can ensure that connectivity is there and we have to only deal with the coverage problem in the network [24].

The aim of WSNs is to maximise the network coverage while minimising the node uses. This is a multi-objective optimisation problem whose coverage model for WSNs is represented by equation 26. In a nutshell, the above problem can be represented as follows:

Input parameters

N: number of sensors

S_j: sensor node set for j (j = 1, 2, . . . , N) i.e. S = (s₁, s₂, . . . , s_i, . . . , s_N)

r: effective radius of all sensors

r_c: communication range, so that for connectivity between two sensor r_c ≥ 2r

A: monitoring area

W, L: represents the width and length of the monitoring area, A

Output parameters

2 - D sets of coordinates values for all N sensors.

redundant information in terms of overlapping area

Objective

First objective is to maximize the coverage i.e. $\max ({Obj}_{1} = area {⋃_{x = 1}^{m} ⋃_{y = 1}^{n} c_{r} (x, y) \cap A})$ (21) where the circle located at (x, y) with radius r is represented by c_r (x, y); the area of a region X is represented by area (X).

Second objective is to minimize the no. of sensors i.e. $\min ({Obj}_{2} = | S^{'} | / N)$ (22) where the total number of the sensor node is represented by N and S′ is the magnitude of active sensors.

Third objective is to minimize the overlapping sensing area between sensors. Obviously, the less the overlapping coverage area, the more will be the coverage within A. Based on this observation a new objective function is designed which is given by

$\begin{matrix} {Obj}_{3} & = \sum_{i = 1}^{N} (\sum_{j = i + 1}^{N} overlap (s_{i}, s_{j}) \\ + \sum_{k = 1}^{4} overlap (s_{i}, b_{k})) \end{matrix}$ (23) where the coverage area for two sensors located at s_i, s_j is represented by overlap (s_i, s_j) and it is given by $overlap (s_{i}, s_{j}) = {\begin{matrix} 0 & if d (s_{i}, s_{j}) > r_{c} \\ {Area}_{overlapping} & if d (s_{i}, s_{j}) \leq r_{c} \end{matrix}$ (24) with d (s_i, s_j) as the Euclid distance between the two sensors s_i and s_j and an expression for Area_overlapping is derived in mathematical formulation for overlapping area section. Equation 24 is illustrated in Fig. 9. The term overlap (s_i, b_k) represents the overlap between the coverage area of sensor at s_i out of monitoring area, A, boundary that is represented by b_k. If d (s_i, b_k) < r then $overlap (s_{i}, b_{k}) = r (r - d (s_{i}, b_{k}))$ (25) where b_k ∈ {(s_i . x, L) , (s_i . x, 0) , (0, s_i . y) , (W, s_i . y)}

Fig. 6

Isosceles triangle obtained from segment of sector.

Fig. 7

Splitting of △ AED.

Fig. 8

Flow chart for IGA-BACA.

Fig. 9

Overlapping criteria.

In a nutshell, the complete objective is to maximize the $maxObj = \max ({Obj}_{1}, 1 - {Obj}_{2}, 1 - {Obj}_{3})$ (26)

5 Simulation results

The monitoring area, A under considering is 100m times 100m with a perception radius, r, of the sensor nodes equals to 10m. A set of 42 working sensor node optimally covers the monitoring area A, as shown in Fig. 10. It is obtained for 300 iteration of IGA-BACA. It is also used as the benchmark for further comparison. The complete algorithm is implemented in MATLAB 2017b. A total of 100 nodes are randomly distributed in the monitoring target area, as shown in Fig. 11.

Fig. 10

Optimal network coverage.

Fig. 11

Random distribution of 100 nodes.

Although the area is covered completely, there exist a lot of redundant nodes which are sensing redundant information. The uncovered areas in A are termed as a coverage hole and in Fig. 11, one can easily detect such coverage holes or blind areas (indicated in red boxes for reference). As compared to the optimal coverage, randomly distributed scenario senses a huge amount of redundant information. Once, the redundant information is expressed in term of the overlapping area, then the overlapping areas is more for the randomly distributed case and minimum for the optimal case. This is illustrated in Figs. 12 and 13.

Fig. 12

Optimal network coverage with overlapping area.

Fig. 13

Random distribution of 100 nodes with overlapping area.

Figure 12 indicates that the overlapping areas of each sensor are equal, which is 86.7546 sq. unit. This concludes that the redundant information sensed by each of the sensors are equal. In contrast, Fig. 13 indicates that the overlapping areas are different for a randomly distributed case, which means each sensor are sensing the different amount of redundant information.

Figures 14 –17 shows the coverage using the IGA-BACA algorithm for 50, 100, 150, 200 generations respectively. As the number of generation is increasing from 50 to 200, the coverage tends towards optimal coverage and hence, the number of redundant nodes decreases.

Fig. 14

50 Generation of IGA-BACA.

Fig. 15

100 Generation of IGA-BACA.

Fig. 16

150 Generation of IGA-BACA.

Fig. 17

200 Generation of IGA-BACA.

To quantify the redundant information relatively, a graph is plotted between the amount of redundant information sensed by the sensors to the no. of iterations or generations, as illustrated in Fig. 18. It has been noticed from Fig. 18 that as the number of iterations is increased, i.e. as the network coverage tends towards the optimal coverage the amount of redundant information sense by the sensor decreases, and also the slope of decrements also increases for higher values of iterations. To evaluate the performance of the combined meta-heuristic over WSNs, the relative redundant information is compared with the existing meta-heuristic approaches, namely GA and ACO.

Fig. 18

Redundant information vs iterations.

6 Conclusion

In this paper we propose an effective way to compute and reduce the redundant information sensed by the sensors in WSNs. It is essential to reduce the overlapping sensing regions as sensing the same set of information results in loss of time and limited energy of the sensors. The optimal coverage is achieved using the combined technique of IGA-BACA. It has been observed that as the number of iterations is increased, the network coverage tend towards optimal coverage. With optimal coverage, the redundant information sensed by the sensors gets reduced to its lowest possible value. Although this approach gives better performance but, much is yet to be explored, especially if one can use other combined meta-heuristic such as lion optimisation, ant lion optimisation etc. to reduce the redundant information.

Footnotes

Acknowledgments

The authors would like to thanks the editor and reviewers for their valuable suggestions.

References

Akkaya

and Younis

, A survey on routing protocols for wireless sensor networks, Ad Hoc Networks 3(3) (2005), 325–349.

Yick

, Mukherjee

and Ghosal

, Wireless sensor network survey, Comput Netw 52(12) (2008), 2292–2330. [Online]. Available: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.comnet.2008.04.002

Rawat

, Singh

K.D.

, Chaouchi

and Bonnin

J.M.

, Wireless sensor networks: A survey on recent developments and potential synergies, The Journal of Supercomputing 68(1) (2014), 1–48.

Farsi

, Elhosseini

M.A.

, Badawy

, Arafat

and ZainEldin

, Deployment techniques in wireless sensor networks, coverage and connectivity: A survey, IEEE Access (2019).

Holland

J.H.

, Adaptive algorithms for discovering and using general patterns in growing knowledge bases, International Journal of Policy Analysis and Information Systems 4(3) (1980), 245–268.

Dorigo

and Birattari

, Ant colony optimization, Springer, 2010.

Yazdani

and Jolai

, Lion optimization algorithm (loa): A nature-inspired metaheuristic algorithm, Journal of Computational Design and Engineering 3(1) (2016), 24–36.

Kulkarni

R.V.

and Venayagamoorthy

G.K.

, Particle swarm optimization in wireless-sensor networks: A brief survey, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 41(2) (2010), 262–267.

Kaplantzis

, Shilton

, Mani

and Sekercioglu

Y. A.

, Detecting selective forwarding attacks in wireless sensor networks using support vector machines, in 2007 3rd International Conference on Intelligent Sensors, Sensor Networks and Information IEEE, 2007, pp. 335–340.

10.

Kulkarni

R.V.

, Forster

and Venayagamoorthy

G.K.

, Computational intelligence in wireless sensor networks: A survey, IEEE Communications Surveys & Tutorials 13(1) (2010), 68–96.

11.

Singh

V.K.

and Sharma

, Elitist genetic algorithm based energy efficient routing scheme for wireless sensor networks, International Journal Of Advanced Smart Sensor Network Systems (IJASSN) 2(2) (2012).

12.

Huang

S.-H.

and Lin

P.-C.

, A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty, Transportation Research Part E: Logistics and Transportation Review 46(5) (2010), 598–611.

13.

Yogarajan

and Revathi

, A discrete ant lion optimization (dalo) algorithm for solving data gathering tour problem in wireless sensor networks, Middle-East Journal of Scientific Research 24(10) (2016), 3113–3120.

14.

Yang

, Zhang

, Ling

, Pan

and Sun

, Task allocation for wireless sensor network using modified binary particle swarm optimization, IEEE Sensors Journal 14(3) (2014), 882–892.

15.

Samadian

and Noorhosseini

S.M.

, Probabilistic support vector machine localization in wireless sensor networks, ETRI Journal 33(6) (2011), 924–934.

16.

Moustapha

A.I.

and Selmic

R.R.

, Wireless sensor network modeling using modified recurrent neural networks: Application to fault detection, IEEE Transactions on Instrumentation and Measurement 57(5) (2008), 981–988.

17.

Sharma

, Singh

, Kumar

and Singh

, Throughputsave ratio optimization in wireless powered communication systems, in 2017 International Conference on Information, Communication, Instrumentation and Control (ICICIC), 2017, pp. 1–6. [Online]. Available: https://doi.org/10.1109/ICOMICON.2017.8279031

18.

Kumar

and Singh

, Throughput optimization for wireless information and power transfer in communication network, in 2018 Conference on Signal Processing And Communication Engineering Systems (SPACES), 2018, pp. 1–5. [Online]. Available: https://doi.org/10.1109/SPACES.2018.8316303

19.

Imran

, Hasbullah

and Said

A.M.

, Personality wireless sensor networks (pwsns), CoRR, vol. abs/1212.5543, 2012. [Online]. Available: http://arxiv.org/abs/1212.5543

20.

Sun

and Tian

, Wsn path optimization based on fusion of improved ant colony algorithm and genetic algorithm, Journal of Computational Information Systems 6(5) (2010), 1591–1599.

21.

Pal

S.K.

and Wang

P.P.

, Genetic algorithms for pattern recognition, CRC Press, 2017.

22.

Wang

, He

and Xue

, Fault diagnosis based on ant colony optimal algorithm, International Journal of Information and Systems Sciences 1(3–4) (2005), 329–338.

23.

Xiong

, Wang

and Yan

, Binary ant colony evolutionary algorithm, International Journal of Information Technology 12(3) (2006), 10–20.

24.

Tian

, Gao

and Ge

, Wireless sensor network node optimal coverage based on improved genetic algorithm and binary ant colony algorithm, EURASIP Journal on Wireless Communications and Networking 2016(1) (2016), 104. [Online]. Available: https://doi.org/10.1186/s13638-016-0605-5.

25.

Weisstein

E.W.

, Circle-circle intersection. [Online]. Available: http://mathworld.wolfram.com/Circle-Circle Intersection.html Accessed: 9 January 2018

26.

On the problem of k-coverage in mission-oriented mobile wireless sensor networks, Computer Networks 56(7) (2012), 1935–1950.

27.

Chen

, Chen

and Li

, Minimum-delay pois coverage in mobile wireless sensor networks, EURASIP Journal on Wireless Communications and Networking 2013(1) (2013), 262. [Online]. Available: https://doi.org/10.1186/1687-1499-2013-262.

28.

Boukerche

and Sun

, Connectivity and coverage based protocols for wireless sensor networks, Ad Hoc Networks 80 (2018), 54–69.