01.12.2016 | Research | Ausgabe 1/2016 Open Access

# Wireless sensor network node optimal coverage based on improved genetic algorithm and binary ant colony algorithm

## Competing interests

## 1 Introduction

## 2 Wireless sensor network coverage optimization

### 2.1 Wireless sensor network coverage

### 2.2 Wireless sensor network optimization coverage model

_{1}, s

_{2}, ⋯, s

_{ i }, ⋯, s

_{ N }). The (x

_{ i }, y

_{ i }) is the coordinate of sensor node s

_{ i }in a target monitoring area A, each node coordinate is known, and effective perception radii are rand s

_{ i }= {x

_{ i }, y

_{ i }, r}. Perception range of node s

_{ i }is a circular region with the coordinates (x

_{ i }, y

_{ i }) of node s

_{ i }as the center and the r as the perception radius, to express with c

_{ i }= {p ∈ A|d(p, (x

_{ i }, y

_{ i })) ≤ r, i ∈ [1, N]}, where, p is an arbitrary point of area A, and d is the Euclidean distance. The perception range of the whole sensor network is C = ∪

_{ i ∈ [1, N]}c

_{ i }, that all network nodes perceptual range are in union.

_{1}, a

_{2}, ⋯, a

_{ j }, ⋯ a

_{ m × n }) need to be monitored or sensed in target monitoring area A; suppose a

_{ j }is s

_{ i }perception then d( a

_{ j }, s

_{ i }) ≤ r; an arbitrary point of monitoring area A is at least perceived by a sensor node. Assume the communication range of sensor node s

_{ i }is a circle with the coordinates (x

_{ i }, y

_{ i }) of node s

_{ i }as the center and the r

_{ c }as the radius; if d(s

_{ i }, s

_{ j }) ≤ r

_{ c }, then the sensor node s

_{ i }and s

_{ j }can communicate directly.

_{ i }, s

_{ j }) ∈ E} composed of S is an undirected graph, if there is a communication path between any two nodes in the communication diagram G derived from S then the communication diagram is connected, when d(s

_{ i }, s

_{ j }) ≤ r

_{ c }.

_{ c }is at least two times perception radius r, namely r

_{ c }≥ 2 r. On this condition, the researchers only need to consider the coverage problem in the sensor network, if the network is covered then it is connected [24].

_{cov}(x, y, s

_{ i }) represent the probability that any point (x, y) of monitoring area A is covered by sensor node s

_{ i }(x

_{ i }, y

_{ i }) then

_{ i }covers the monitoring point (x, y) then the monitoring point (x, y) is covered by the sensor node set S. So the regional coverage area of sensor node set k is expressed as follows:

_{ s }, the working sensor node set is S′, the target function of network coverage of working node set is as follows:

_{area}(S′) is the cover area of working sensor node set S′.

## 3 Improved genetic algorithm and binary ant colony algorithm

### 3.1 Genetic algorithm

_{ c }is exchanging probability, P

_{ m }is mutation probability, f

_{max}is the biggest fitness of colony, f

_{avg}is the average fitness of colony, f′ is the bigger fitness of two strings used for crossover, f is the fitness of the individual to mutate.

### 3.2 Binary ant colony algorithm

_{ s }is the start vertex, \( {c}_j^0\kern0.1em ,\kern0.3em {c}_j^1 \), respectively, stand for the 0 and 1 states of bit b

_{ j }in binary-coding. For all vertex, when j = 2, 3, ⋯, N, there are only two directed arcs which point to \( {c}_{j-1}^0 \) and \( {c}_{j-1}^1 \), these two directed arcs respectively stand for the 0 and 1 states of each ant next step allowed, the N is the binary encoding length, this binary ant colony network is shown in Fig. 1. Each ant travels their own path and then get the solution of the problem by integrating each ant’s traversal solution [26–31].

_{ i,j }(0) = C (C is a constant), Δτ

_{ i,j }= 0 (i, j = 1, 2, ⋯, N). In the process of movement, the k (k = 1, 2, ⋯, M) ant determines the movement direction according to the information quantity of each path, and the movable probability is

_{ i,j }is the residual information amount in the i j connection at the t moment. η

_{ i,j }is the visibility in the i j connection. allowed

_{ k }= {0, 1} is the next select status.

_{ i,j }is renewed as follows:

_{ i,j }= 1/f

_{best}(S), f

_{best}(S) is the iteration-best solution or global best solution, which can enhance the optimizing ability and improve the speed of solution.

### 3.3 Improved genetic algorithm and binary ant colony algorithm

## 4 Wireless sensor networks nodes optimal coverage based on IGA-BACA

_{1}, s

_{2}, ⋯, s

_{ i }, ⋯, s

_{ N }), seeking the working set S′, which can obtain the maximum network coverage rate, and the minimum working node set. When the maximum network coverage rate is selected as the optimal objective, network sensor nodes with hexagon structure distributed in the monitoring area, the minimum working nodes set can be obtained [33].

_{1}(S′) and minimum working nodes set f

_{2}(S′) are contradictory; compromising the two, the multi-objective optimization coverage model of wireless sensor network is changed into the maximum objective function f(S′).

### 4.1 Code

_{1}, l

_{2}, ⋯, l

_{ i }, ⋯, l

_{ N }) of wireless sensor node is expressed in a binary coded form, which stands for the position of all sensor nodes in the target monitoring area A, where the l

_{ i }value is 1 or 0, which separately correspond to the active or sleep of the i sensor node. The selection of nodes and the gene of chromosome is one to one correspondence.

### 4.2 Initial solution and adaptation function

### 4.3 Operation operator

_{ c }then it can produce two new individuals by exchanging parts of chromogene stochastically. The two-point crossover is adopted in this paper, randomly generating two crossover points is shown in Fig. 5. The genetic algorithm can generate filial generation colony which have higher average fitness and better individuals through the reproduction and crossover operators and can make the evolutionary process proceed to the optimum solution.

_{ m }, namely turning 0 to 1 and 1 to 0. The mutation operator is very important to recoup the loss of colony diversity.

_{ g }) is a mapping of pheromone update for optimal individual which is selected from an ant sequence. According to the Max-Min rule, pheromone only be released in the path of optimal solution ant traverse, namely Δτ

_{ i,j }= 1/f

_{best}(S), f

_{best}(S) is the iteration-best solution or global best solution. The probability of pheromone update operator is shown as follows:

### 4.4 Ants traverse

## 5 Simulation experiment

Evolution generations | IGA-BACA | GA | ||||
---|---|---|---|---|---|---|

Network coverage rate (%) | Working set node number | CPU-time (s) | Network coverage rate (%) | Working set node number | CPU-time (s) | |

– | 100 | 45 | – | 100 | 45 | – |

50 | 93 | 63 | 11 | 93.1 | 65 | 13 |

100 | 95.2 | 56 | 21 | 94.3 | 59 | 25 |

150 | 96.5 | 51 | 31 | 95.6 | 53 | 37 |

200 | 97.5 | 48 | 42 | 96.2 | 50 | 49 |