Abstract: The performances of wireless sensor network heavily depend on topology which is formed by sensor nodes’ deployment. In order to increase coverage area of Wireless Sensor Network, decrease redeploying times and energy consumption, a novel coverage algorithm named CSAPO was proposed in this study. CSAPO deployment strategy was designed through combining artificial physics optimization algorithm and clonal selection algorithm, where the movement direction of particle is together determined by artificial physics optimization and clonal selection algorithm. In this research, Artificial physics optimization was devoted to update the main motivation and the clonal selection algorithm was used to help artificial physics optimization to avoid trapping local optimum. Simulation results showed that performances of algorithms such as final coverage rate, convergence speed and total moving distance are improved significantly compared with artificial physics optimization and particle swarm optimization. At last, the impact of mutation constant Cm on performances was analyzed.
INTRODUCTION
Wireless Sensor Network (WSN) consists of many distributed low-cost smart sensor nodes integrating sensing, processing and communication capabilities to monitor environment conditions. It has been widely applied in harsh environment monitoring, surveillance, healthcare and military (Gaur and Garg, 2010; Tan et al., 2012). Compared with traditional methods of data collection, WSN inspires more research interest for its huge application promise (Chen et al., 2012).
Deployment is one of most important issues in WSN and it is also a key for evaluating the quality of service (QoS) of WSN. The aim of deployment is to maximize the coverage percentage which can improve target detection probability and enhance the performance of network (Wang et al., 2006; Nadeem et al., 2007).
Due to limited sensing range and not enough sensors to cover the whole monitoring field, the deployment algorithm is more vital in topology control (Aziz et al., 2009; Ghosh and Das, 2008). Virtual Force Algorithm (VFA) and Particle Swarm Optimization (PSO) are widely used for solving coverage problem recent years. Zou and Chakrabarty (2004) proposed a novel probabilistic target localization algorithm based on VFA and its application in maximizing coverage. An expression of exponential function for the relationship of virtual force is proposed to converge rapidly (Chen et al., 2007). A distributed mobility assisted probabilistic coverage protocol which was modified from VFA algorithm was put forward by Wang et al. (2006). The Particle Swarm Optimization (PSO) is a global optimization algorithm which was developed by Kennedy and Eberhart (1995). It optimizes a problem by iteratively searching batter candidate solution with a given initiation solution. The suitability for WSN applications was discussed by Kulkarni and Venayagamoorthy (2011). A dynamic deployment algorithm which combined VFA and PSO was proposed by Wang et al. (2007). Three dynamic PSO-based deployment algorithms that reduce the computation time are designed by Soleimanzadeh et al. (2010).
Slow global convergence speed and quick prematurity are the problems with using a solo algorithm (Lee and Lee 2012; Huang et al., 2012), while fusion of kinds of algorithms can provide excellent performance over employing them individually (Wang et al., 2008).
Therefore, in this study a hybrid Artificial Physics Optimization (APO) algorithm based on combining Clonal Selection Algorithm (CSA) and APO together which called CSAPO is proposed.
APO is a new population-based stochastic algorithm presented recently years
which is inspired from Physicomimetics framework and used to solve global optimization
problems (Xie et al., 2011a). In APO framework,
particle is driven by virtual physics forces
CSA is a class of algorithms inspired by the clonal selection theory in Artificial immune systems (Cutello et al., 2006). Though introducing diversity keeping mechanism, various concentration ranks of particles will be maintained at a certain amount which can speed up convergence of APO. In this paper in order to improve the performances of coverage algorithm, we put forward a new concentration formula for CSA.
MATHEMATICAL MODEL
Sensing model: The sensing gradient of node attenuates gradually as the distance increase. The sensitivity S of a sensor si at point P is usually modeled as follow (Ghosh and Das, 2008):
| (1) |
where, λ and k are sensor-dependent parameters, ||xs-xP|| is the Euclidean distance between the sensor and the point.
Coverage model: For any point P, we denote the Euclidean distance between si and P as d(si, P) = ||xs-xP||, binary sensor model shows as Eq. 2:
| (2) |
In fact, because of noise jamming, sensor detection is imprecise. The probabilistic terms of coverage cxy(si) are written as Eq. 3:
| (3) |
Total coverage of point P as follows:
| (4) |
where, S is the set of nodes whose sensing range cover the point P, k is total numbers of nodes whose sensing range cover the point P.
THE PRINCIPLE OF CSAPO ALGORITHM
In APO, each individual has different mass and holds its own velocity and location in n-dimensional problem space (Yin et al., 2010). For particle i, xi(t) = (xi1, xi2) denote its current position, where xi1 represents x-coordinate of ith particle, while xi2 represents y-coordinate of ith particle.
Defination 1: Xi(t+1) = (x1(t+1), x2(t+1),... xi(t+1), xi+1(t)) is the position vector of all nodes in APO stage. F(Xi(t)) is the coverage rate value which is obtained on condition that first i particle update their position at t iteration.
xi, best(t) denotes its own local best position in APO stage, f(Xi, best(t)) is the coverage rate value at the best position of ith particle up to t iteration, where, xi, best(t) is updated as follow:
| (5) |
There are two main parts of APO algorithm which are: calculation force and motion. In the part of calculation force, we define a force law:
| (6) |
where, m denotes the mass of individual, the mass function of ith particle is calculated as follow:
| (7) |
In which, fbest(t) is the coverage rate value at the best position of particle at t iteration, where, fbest(t) = max{f(X1, best(t)), f(X2, best(t)),..., f(Xn, best(t))}, n is the total number of particles and fworst(t) is the coverage rate value at the position of the worst individual, fworst(t) = min{f(X1, best(t)), f(X2, best(t)),..., f(Xn, best(t))}, n is the total number of particles.
Then the APO force which is exerted on each individual by all other individuals is computed by follow law:
| (8) |
where, Fij,d(t) is the d-coordinate force exerted on particle i by particle j, xi,d(t) and xj,d(t) are the dth-dimension coordinates of particles i and j, respectively. The d-coordinate force of the total force Fi,d(t) exerted on individual i by all other particles is obtained by following equation:
| (9) |
In motion step, we use the previously computed total force to calculate the velocity of particles and then update the particles’ positions. The velocity and position of particle i is updated as follows:
| (10) |
| (11) |
where, vi,d(t) and xi,d(t) are the dth-dimension coordinates of particle i’s velocity and position at generation t. α(t) is a random functions distributed on [0,1]. ω(t) is the inertia weight, with the increasing of iterations, it should be reduced, the updating formula of ω(t) can be written as Eq. 12 (Chen et al., 2007):
| (12) |
Here, nmax is truncated generation, t is current iteration number. Figure 1 show the calculation method of coverage rat. Figure 2 shows the pseudo code for the APO algorithm.
The clonal operator can be divided into 3 stages:
| • | Clone stage: In this stage, ith particle is copied as ni,c same particles in the solution space according to its concentration function. ni,c is determined by Eq. 13 |
| (13) |
Here n is the population size, j is the serial number, obtained by the descending order of Di which is the particle concentration.
Particle with higher coverage rate is always hoped to generate more particles, it is hard to keep diversity of particles and easy to trap in local optimum. Those particles which locate low coverage rate position but have a good evolutionary trend will be ignored.
| Fig. 1: | Pseudo code for calculation method of coverage rat |
| Fig. 2: | Pseudo code of APO algorithm (APO represents artificial physics optimization) |
In order to avoid the problem listed above, Di is calculated as follow:
| (14) |
Here, nni(t) is numbers of particles covered with ith particle’s sensing range.
| • | Mutation stage: Gaussian mutation and cauchy mutation are the common mutation methods. In this paper we chose Gaussian Mutation as mutation algorithm. The new position of kth (k<nni(t)) cloned particles which was generated by ith particle is calculated according to Eq. 12 |
| (15) |
Here, Cm is mutation constants, N(0, 1) is a Gaussian random number.
| • | Selection stage: In this stage, the poison corresponding to particle that has the max coverage rate among the ith particle and its cloned particles was selected as the new position of ith particle |
Figure 3 shows the implementation details for CSA and pseudo code of CSAPO is shown in Fig. 4.
SIMULATION RESULTS
In this section the performances of APO, PSO and CSAPO algorithms under probabilistic model with different scenarios will be simulated. The common simulation parameters are set as follow: Rs = 3, Ru = 0.6xRs, Rc = 2xRs β = 0.5, γ = 0.5, G = 1, βcs = 0.4, Cm = 1.
Comparison of effective coverage rate: At first, the results of a scene including 70 nodes are shown. Figure 5 shows the initial locations of sensors where the effective coverage is 50.88%.
| Fig. 3: | Pseudo code of CSA (CSA represents clonal selection algorithm) |
| Fig. 4: | Pseudo code of CSAPO (CSAPO is the name of a new coverage algorithm proposed in this study) |
Figure 6 shows the final sensor positions determined by APO algorithm and the effective coverage is 82.24%. Figure 7 shows the final sensor positions determined by PSO algorithm and the effective coverage is 81.28%. Figure 8 shows the final sensor positions determined by CSAPO algorithm which effective coverage is 84.16%.
Then the performances of APO, PSO and CSPSO on effective coverage rate under 5 different network size with n = 50, 60, 70 80 and 90 are investigated. Fifty independent operations with different network size are carried out; the result is illustrated in Fig. 9. The average coverage rates of CSAPO are 60.53, 72.59, 83.54, 92.53 and 98.38% respectively when n = 50, 60, 70 80, while these of APO are 57.82, 70.53, 81.38, 91.01 and 96.96%, these of PSO are 57.92, 69.82, 80.86, 91.18 and 96.00%.
| Fig. 5: | Initial locations of sensors |
| Fig. 6: | Sensor positions after the execution of APO, APO: Artificial physics optimization |
| Fig. 7: | Sensor positions after the execution of PSO |
| Fig. 8: | Sensor positions after the execution of CSAPO CSAPO: Name of a new coverage algorithm proposed in this study |
From the simulation following facts can be obtain: (1) the coverage rate of CSAPO is larger than that of the other algorithms and (2) effective coverage rate of CSAPO based on probabilistic model respectively increase 4.69, 2.92, 2.65, 1.67 and 1.46% compared with APO in the case of 50, 60, 70, 80 and 90 nodes. Compared with PSO, the numbers are 4.51, 3.97, 3.31, 1.48 and 2.48%.
This is because APO algorithm under mass function shown in this study has a best performance (Xie et al., 2011b) and CSA can help APO void premature convergence and guarantee the diversity of the population (Lu, 2009).
Table 1 shows the convergence speed with 50 independent operations under n = 70, 80, 90. The convergence speed of CSAPO based on probabilistic model, respectively decrease by an average of 13.2 and 18.7% compared with APO and PSO.
This is because CSA can guide the particle to the region in which there are not many particles (Mitra and Venayagamoorthy, 2008) and the blindness of the particle’s movement is rare, therefor performances of coverage rate and convergence speed are enhanced.
| Fig. 9: | The coverage rate under different network size (50 independent operations) |
| Table 1: | Convergence speed with 50 independent operations under different network size |
| 1APO represents artificial physics optimization, 2PSO represents particle swarm optimization, 3CSAPO is the name of a new coverage algorithm proposed in this study | |
According to Xie and Zeng (2010), the convergence speed of APO is faster than that of PSO, while in this study the result is reverse, this is because the virtual force used in this study is not the most effective form.
Comparison of moving distance: Here, energy consumption during the period of nodes redeploying is investigated though total moving distance of all the sensor nodes in each round. Table 2 shows the moving distance in case of 70 nodes with 50 independent operations.
The simulation results indicate that compared with APO and PSO, the moving distance of CSAPO based on probabilistic model, respectively decrease by an average of 18.68 and 13.21%.
Motion of particle is determined by APO and CSA, this can decrease repetitive movement, thereby CSAPO will obtain high coverage rate with low cost in term of moving distance.
Impact of coefficient on performance: This section influence of mutation coefficient Cm on the algorithm performance will be discussed-CSAPO’s performances on effective coverage rate, moving distance and convergence when Cm = 1, 10, 50, 70 under n = 50 are investigated.
| Table 2: | Moving distance in case of 70 nodes with 50 independent operations |
| 1APO represents artificial physics optimization , 2PSO represents particle swarm optimization, 3CSAPO is the name of a new coverage algorithm proposed in this study | |
| Fig. 10: | Convergence curve when Cm = 1, 10, 50, 70 |
| Fig. 11: | Moving distance per round when Cm = 1 |
The simulation results based on probabilistic sensor model are shown in Fig. 10.
As shown in the simulation results, when Cm = 1 the effective coverage rate is 59.96%, while the values are 58.88, 58.51 and 58.34% when Cm = 10, 50, 70. When Cm = 1, the algorithm can quickly converge to a global optimal with 112 iterations, the algorithm with Cm = 10, 50, 70, respectively converge to optimal after 136, 153 and 176 iterations.
| Table 3: | The performances with 50 independent operations under different Cm |
| Cm is mutation constant | |
| Fig. 12: | Movement traces when Cm = 1 |
| Fig. 13: | Moving distance per round when Cm = 10 |
Without loss of generality, 50 independent operations with different Cm are carried out and the effective coverage rate and convergence speed are illustrated in Table 3.
The total moving distance are respectively 1000.5, 1078.3, 1228.1, 1322.4 when Cm = 1, 10, 50, 70. Figure 11-18 show the total moving distance and the movement traces of all nodes. These figures obviously show that movements of particles under Cm = 1 are not frequent and the moving distance of each round is short.
| Fig. 14: | Movement traces when Cm = 10 |
| Fig. 15: | Moving distance per round when Cm = 50 |
| Fig. 16: | Movement traces when Cm = 50 |
Combining with Table 3, the simulation results indicate that the value of effective coverage rate and convergence speed decrease with the increase of Cm and the moving distance increase with increasing Cm.
| Fig. 17: | Moving distance per round when Cm = 70 |
| Fig. 18: | Movement traces when Cm = 70 |
This is because particles are in relatively good position after APO is executed and long distance moving is not needed for particle.
CONCLUSIONS
In this study, a hybrid sensor deployment strategy of WSN called CSAPO which combines CSA with APO is proposed and probabilistic model is used to evaluate the performances of this algorithm. In CSAPO algorithm APO has good global search ability, while CSA is good at local searching, that can speed convergence speed and coverage rate. Simulation results illustrate that compared with APO and PSO the final coverage rate of CSAPO based on probabilistic model respectively increase by an average of 2.67, 3.15%. The convergence speed of CSAPO based on probabilistic model respectively decrease by an average of 13.2, 18.7% compared with APO and PSO. The moving distance of CSAPO based on probabilistic model, respectively decrease by an average of 18.68, 13.21%.
ACKNOWLEDGMENT
Financial support for this works which provided by State Key Laboratory of Integrated Service Networks under grant ISN10-10.
NOMENCLATURE
| Rs | : | Detection range of sensor node |
| Ru | : | Measure of the uncertainty in sensor detection |
| β, γ | : | Parameters that measure the detection probabilities when an object is within a certain distance from the sensor |
| Rc | : | Communication range of sensor node |
| G | : | Gravitational constant |
| β | : | A random number distributed on [0,1] |
| Cm | : | Mutation constant |