1 Introduction

With the research of wireless directional sensor network^[1-4], the problem of wireless sensor network coverage has received extensive attention. The conventional directional sensor models are almost 2D models^[5-8]. However, sensor nodes are dispensed in real 3D physical world. The 2D sensor model and its coverage enhancement algorithm can not be used in the real world.

A 3D directional sensing model and a coverage enhancement algorithm which is based on virtual force are established by Ma ^[9]. Based on this model, Wang^[10] and Xiao^[11] proposed models which are based on the pitch angle and the deviation angle. However, due to the high complexity computation, the coverage enhancement strategies of the two models are based on 2D graphic. So in order to construct a 3D directional sensor model and the corresponding coverage enhancement algorithm which conform to the real environment, a new 3D directional sensor model and the coverage enhancement algorithm are proposed.

However, if sensing direction of one node has been changed, it maybe impacts other adjacent nodes. So it is a NP problem^[11]. The most effective way to solve the NP problem is adopting intelligent optimization algorithm^[12-15].

The gravitational search algorithm ^[16-17] is one of the best optimization algorithms and it will be adopted to enhance the coverage rate of directional sensor network. The directional mutation strategy and the evolutionary strategy are proposed to enhance the global search ability and local exploitation ability of gravitational search algorithm. Then a coverage enhancement algorithm is proposed which is based on the improved gravitational search algorithm.

2 New 3D Directional Sensing Model 2.1 3D Sensing Model

Multimedia sensor nodes are located in three-dimensional physical space. Different from the traditional simplified model, our 3D directional sensor model depends on the location of the node, the pitch angle, the deviation angle, sensing radius and visual angle. The sensing model can be described as P, γ, θ, α, R, P^′.Where P(x₀, y₀, z₀)is the location of node in three-dimensional physical space and P′x, y, z is the intersection point of the main direction of perception and the spherical surface of sensing region, γ is the pitch angle which PP′ project in the vertical direction and θ is the deviation angle which PP′ project in the horizontal direction.α is the visual angle of the node;R is the sensing radius of node. The model is shown in Fig. 1.

For the 3D directional sensing model, we need to judge whether a point has been covered by a node. In this paper, if the point M satisfies the following two conditions, we can say it has been covered.

$\left\{ \begin{align} & \left\| PM \right\|\le R \\ & \delta \le \alpha /2 \\ \end{align} \right.$

(1)

where δ is the angle between $\overrightarrow{PM}$ and $\overrightarrow{P{P}'}$.

3 Coverage-Enhancement Algorithm Based on Improved Gravitational Search Algorithm

Overlapped coverage between sensor nodes is the main factor to impact the coverage rate of directional sensor nodes. So we must reduce the overlapping area of directional sensor network. In this paper, monitoring direction will be decomposed by the pitch angle and the deviation angle. And if we adjust the two angles, the direction of the monitoring node can be adjusted. However, if the direction of one node has been adjusted, it maybe impacts the direction of other adjacent nodes. It is a NP problem. And the most effective way to solve the NP is adopting intelligent optimization algorithm.

3.1 Improved GSA

GSA is one of the most excellent optimization algorithms at present. And we will adopt the GSA to adjust the pitch angle and the deviation angle. In order to enhance the optimization ability, individual evolution strategy and directional mutation strategy will be proposed to improve GSA.

(1) Individual evolution strategy.

The original algorithm has a strong global searching ability. However, if algorithm makes much focus on global search, it will lead to the population with a slow convergence. In order to improve the convergence speed of the algorithm, the individual evolution strategy is proposed in this paper. And we will describe it as follows:

When particles of population get better solutions, we can make use of the evolutionary trend to get best solutions. If a particle gets a better solution at current iteration, we can calculate the changing degree of particles in each dimension and perform the corresponding changing degree to this particle until do not meet a judgement conditions.

The individual evolutionary strategy has two advantages:

1) The population can converge into a better regional rapidly;

2) The particle move toward to the evolutionary trend of their own, although does not move toward to the current optimal solution, but it can keep the diversity of population and reduce the probability of falling into local optimum.

At the early stage of evolution, the distribution of particles is more dispersed and easy to get a better solution. At the later stage of evolution, the distribution of particles is more concentrated and the particle is hard to get a better solution. Therefore, the judging condition will be changed with different stages of population evolution. The judging condition of whether use the individual evolutionary strategy can be described as follows:

$\left| {{f_i}\left( {t - 1} \right)} \right| \times {\left( \eta \right)^{\frac{t}{T} - 1}} < \left| {{f_i}\left( t \right)} \right|$

(2)

where f_i(t－1) is the fitness value of particle i at time t-1; f_i(t) is the fitness value of particle i at time t, η is a random number in the interval[0 1].

When a particle meets the conditions (2), calculate the change rate of the particle i at kth dimension between time t and time t-1 and it can be described as follows:

$l_i^k = \frac{{X_i^k\left( t \right)}}{{X_i^k\left( {t - 1} \right)}}$

(3)

where X_i^k(t－1) is the position information of particle i in the kth dimension at time t-1; X_i^k(t) is the position information of particle i in the kth dimension at titeration; l_i^k is the change rate between X^k(t) and X_i^k(t－1). Then using the change rate to get a new particle and it can be described as follows:

$\overset\frown{X_{i}^{k}(t)}=l_{i}^{k}\times X_{i}^{k}$

(4)

where $\overset\frown{X_{i}^{k}(t)}$ is the predictive value and compare its fitness with X_i^k(t) and select the best one.

(2) Directional mutation strategy.

The diversity of population will decrease gradually with continuous optimization. And the population is easy to fall into local optimum. The optimization progress will stop with no other mechanisms. In order to solve this problem, a directional mutation strategy is proposed in this paper.

In the early stage of evolution, particles are dispersive distributed in the space. And the evolution of each individual is affected by other individuals. In order to maintain the diversity of the population, early variation of particle should disturb around itself. In the later stage of evolution, the particles converge into a small region gradually. And a variation strategy will be adopted to prevent population fall into local optimization.

Based on the above analysis, the disturb method can be described as follows:

$\eqalign{ & x_i^k(t + 1) = \left( {1 - \frac{t}{T}} \right) \times x_i^k(t) + \left( {\frac{t}{T}} \right) \times x_{best}^k(t) + \cr & c\left( {{r_1} - 0.5} \right) \times \left( {{r_2}x_{best}^k(t) - x_i^k(t)} \right) \cr} $

(5)

where r₁and r₂ are random number in the interval [0, 1].

In the early stage of evolution, the disturbance is around the current particles. And with the iterations increasing, the parameter of x_i^k(t) will decrease gradually and the parameter of x_best^k(t) will increase gradually. The center of the disturbance will be changed from the current particle to the better particle. The disturbance strategy can avoid the population fall into local optimum and enhance the local exploitation ability of the algorithm. The new variation individual will be compared with the old one and retain the better one.

We define D as the dimension of the problem and N as Population size. The complexity of GSA is O(N2D) and the complexity of directional mutation strategy and individual evolution strategy is O(N2D) +3N). If N>2, the complexity of our algorithm is also O(N2D).

3.2 Fitness Function

When use the optimization algorithm to optimize the coverage rate, we need to set the fitness function for algorithm. Because reducing coverage rate is our object, it will be selected as fitness function. Discrete points at intervals of △x in x axis direction, Δy in y axis direction and △z in z axis direction is selected to discrete the monitoring region, thus the coverage of scene is transformed into coverage of the discrete points set. Assuming that the points set of the discrete monitoring region is Ω, and point set covered by at least one sensor node is Ω₀, then coverage rate η is defined as:

$\eta = \left\| {{\Omega _0}} \right\|/\left\| \Omega \right\|$

(6)

3.3 Description of Coverage-Enhancing Algorithm

The directional sensor nodes are deployed in the monitored region in random way and the number of nodes is n. So the number of pitch angle and the deviation angle are n. Because the two angles are the optimized variable, the dimension of population is 2n.

The deviation angle of node is described by the first dimension to the n dimension of population and the pitch angle of node is described by the n+1 dimension to the 2n dimension of population. And the step can be described as follows:

Step 1 Initialize the deviation angle and pitch angle for each particle and each particle represent a monitoring method；

Step 2 Calculate the fitness for each particle；

Step 3 Update the G, best and worst of the population；

Step 4 Calculate M and a for each particle；

Step 5 Adopt the individual evolution strategy；

Step 6 Adopt the mutation strategy；

Step 7 If it satisfies the termination conditions, to calculate the final coverage.

The flow chart can be seen in Fig. 2.

4 Simulation 4.1 Parameters of Simulation

In this section, the proposed algorithm IGSA will be compared with ABC^[18-19], PSO^[20] and GSA on the coverage problem of three-dimensional. And each directional sensor node has the same visual angle and sensing radius. The sensor nodes are deployed in the monitoring area randomly and they only need to report its initial position and receive the adjustment of the pitch angle and the deviation angle.

The simulation parameters of the coverage-enhancing algorithms are shown in Table 1.

For directional sensor network, the area coverage rate is affected by the number of nodes, sensing radius and visual angle. So three groups experiment will be operated to research the impact of these parameters on coverage-enhancing algorithms of directional sensor networks and compare our algorithms with ABC, PSO and GSA.

4.2 Simulation and Analysis

In order to observe the diversification of coverage, the figure of space coverage will be given and main parameters are listed in Table 1. Fig. 3(a) shows the initial coverage rate of wireless directional sensor network. And the coverage rate is 41.54%. After using our coverage enhancement algorithm, the final coverage rate is 51.79%. Fig. 3(b) shows the final coverage case.

4.2.1 Impact of number of nodes

The object of this section is to research the impact of the nodes number on coverage-enhancing algorithms of directional sensor networks. Keeping other main parameters in Table 1 and c hanging the number of nodes from 10 to 70. The experiment results are shown in Table 2.

From Table 2, we can see that with the increase numbers of nodes, the coverage rate of four algorithms and random coverage have increased obviously. IGSA always has the highest coverage rate than other algorithm. When the number of nodes is small in the monitoring area, the overlapped monitoring area among the nodes is small. So the difference of the coverage rate of the four algorithms is very small. But when there are many nodes in the monitoring area, our algorithm keeps a highest coverage rate than the other two coverage-enhancing algorithms.

4.2.2 Impact of the sensing radius

The object of this section is to research the impact of the sensing radius on coverage-enhancing algorithms of directional sensor networks. Keeping other main parameters in Table 1 and c hanging the sensing radius from 10 m to 50 m.The experiment results are shown in Table 3.

From Table 3 , we can see that with the increase of the sensing radius, the coverage rate of three algorithms and random coverage all have increased obviously.And IGSA has the highest coverage rate than other algorithms. When the sensor node has a small sensing radius, the monitoring area of each node is small and the area of overlapped is small. So the coverage rate of the three algorithms has small differences. The area of overlapped will increase with the sensor node has a large sensing radius.And our algorithm has a highest coverage rate than the other three coverage-enhancing algorithms.

4.2.3 Impact of visual angle

The object of this section is to research the impact of the visual angle on coverage-enhancing algorithms of directional sensor networks. Keeping other main parameters in Table 1 and c hanging the visual angle from π/6 to π. The experiment results are shown in Table 4 .

From Table 4 , we can see that with the increase of the visual angle, the coverage rate of three algorithms and random coverage all have increased obviously. IGSA always has the highest coverage rate than other algorithms.

5 Conclusions

This paper proposed a new 3D directional sensor model based on pitch angle and deviation angle. And in order to enhance the coverage rate of the network, a coverage enhancement algorithm based on improved gravitational search algorithm is proposed. The improved strategies are directional mutation strategy and the evolutionary strategy which make better balance on the ability of global search and local exploitation ability of GSA. Through the extensive simulations experiments, it can be demonstrated that IGSA has a good searching ability and coverage enhancement algorithm can get a best coverage performance than the other algorithms.