Sensor Deployment for Optimal Coverage: BFO Approach

Sensor Deployment for Optimal Coverage: BFO Approach

Abstract: The placement of sensors in given physical space is a critical parameter to be considered while studying the effectiveness of sensing network. The sensors may be deployed in a determined or a random order according to the monitoring sense of coverage. The random deployment provides better coverage in case when sensors are to deployed in large physical space or when condition are harsh at target area. Optimal coverage to target area is provided by using efficient deployment algorithms based on optimization techniques. In this paper, two deployment approaches based on Genetic Algorithm and BFO Algorithm is proposed to optimize the coverage provide by sensors. These approaches minimize overlapping (fitness) amongst the sensors in order to increase the coverage. As the fitness value decreases the coverage percentage increases in both the approaches.

Keywords: Deployment, Coverage, Genetic Algorithm, Bacterial Foraging Optimization (BFO) Algorithm

1. INTRODUCTION

   The information of the physical space is essential to build up valuable knowledge of the environment. In harsh environment, remote accurate observations are required for sensing natural parameters. Recent advances in electronics have led to development of sensors for their type of observations from which the information is derived. The process of analyzing the information to trace changes in the state of physical space over time is called monitoring and that depends on the accuracy of the parameters sensed in the physical space under study [20]. These sensor nodes deployed in the particular area to sense the information and to transmit this information to base station. These nodes have been deployed mainly in those areas in which human interaction is not possible. The sensors may be deployed randomly or in a determined order with taking into consideration the sense of coverage. As follows:

   • Target coverage When the number of targets, with existing locations are to be regularly observed, maximum sensors are stochastically deployed close to target [2].

   • Barrier coverage To observe movement on national border, sensors are deployed in a line along with the border to monitor every inch [2].

   • Blanket or full coverage Covering entire physical area that is every single point is in the sensing range [2].

     In the blanket coverage, various approaches have been used to maximize coverage with the minimum number of sensors. The random deployment is carried out only in case of large physical space otherwise the sensors can be deployment in a determined manner. However, in case of random deployment a problem of hole formulation in the coverage is encountered that is solved by using efficient deployment algorithms [3] [7].

     The sensors may be deployed in static, dynamic or hybrid manner depending upon the situation of observation being sensed by the network. All nodes could be considered as mobile nodes to maximize the coverage in the first approach of hole formulation. In the second approach named as hybrid approach in which some node would be static (stationary) nodes and efficient algorithm would determine locations and number of mobile nodes to be deployed in order to get maximum coverage [18].

     In WSN, the major issue is of the energy consumption, because in sensors utilized the battery energy for sensing the information, to transmit the information to neighbor nodes. Once the energy provided to the nodes is the net amount of energy that can be utilize no extra energy can be provided to the system.

     In WSN, the sensed data from physical space is to be communicated to base station that is done with hop-by-hop link among the neighbor nodes, the failure of which would result in disconnected pieces of sensor network.

     1. Communication Models of WSN

   • Unit Disc: In the Unit Disc model, the communication among the nodes of the network depends on sole distance between the nodes [19].

   • Empirical Network (Instance Model): Other factors such as radio, transmission power type and antenna height are significant [19].

     1. Sensing Models

   • Boolean Sensing Model In this model, the sensing area of node is the area of the circle with radius isometric to the sensing range of the node. The effect of environment and other emitted signals at the time of detection are ignored [18].

   • Probabilistic Model In this model, the probability of detection of event depends on environmental factors.

     k, l))

     (i.e., nutrient concentration effected due to addition of cell attractant ).

     1. Assume Mlast= M (i, j, k, l) to store the parmeter , since there are chances of finding better fitness value in another iteration.

     2. Tumble:this step generates a vector ( random) r (i)

        Rp with every element m (i), m = 1, to P

     3. Move: Let

        di (j+1, k, l) =di (j, k, l) + C(i)×(i)/

        movement happens in the tumble direction with distance equal to step size

     4. Compute J (i, j+1, k,l) and

     let J (i, j+1, k,l)=J(i, j, k, l)+Jcc (i (j+1,k,l),P(j+1,k,l))

     The sensing ability of node is not uniform as it depends on the fading parameter. Elf's sensing and Shadow Feeding sensing model is a probabilistic model [18].

2. SOFT COMPUTING APPROACHES

   // Initialization

   1 generate initial population of size PS randomly;each population IP represent (x,y) coordinate of n mobile sensor and all sets of population are represented PUSH

   // Loop until the terminal condition 2 for i=1 to I; number of iterations

   3 calculate the fitness of each population. fitness is given by overlapping area calculated by square matrix. Sort the populations as per fitness value is ascending order.

   4. population with minimum fitness value are Selected and saved as IP the best population are saved for next iteration;

   // Crossover

   1. for j=1 to m do two solution from IP are picked randomly IPi and IPj;

   2. generate IPq and IPr by one-point crossover to IPi and IPj;

   3. IPq and IPr are saved to IP ; 8 end for

   // apply mutation with probability Pm 9 for j=1 to m do

   1. IPi is selected from IP;

   2. Even bit of solution IPi is exchanged with odd bit and vice versa to produce new solution IPi(n) ;

   3. check feasibility of IPi(n) is unfeasible

   4. if feasible update PUSH by replacing IP i with IPi(n);

   5. endif 15endfor

   // Updating

   // Returning the best solution

   16 return the best solution(x,y coordinates of mobile sensors) with minimum fitness value out of IP.

   Let m = m+ 1

   Swim

   Let m=0 (counter for swim length)

   While m < Ns (if have not climbed down too

   g)

   i)

   ii) long)

   • Deployment Approach based on GA

     If J (i, j+1, k,l)<Jlast (if doing better), Let Jlast = J (i, j, k, l)

     & let

     i(j+1, k, l)=i( j, k, l)+C(i)×(i)/ (j

     M (i, j+1, k, l) is identical in step (f)

     • Else, assume m = Ns. it indicates end of while loop

     h) increment (i) condition i ~=S . In order to proceed return to [b] which is next bacterium

     [Step 5] If j< Nc, return control at step 4. If bacteria life is not over continue.
     [Step 6] Reproduction

     a) For the given k and l, and for each i=1,2,.S, let

   • Deployment approach based on BFO

     [Step 1] Initialize parameters

     Population(p),quantity of bacteria(S), step number (Nc), swim boundary (Ns), steps for reproduction (Nre), event count (Ned), Probability of elim./disp.(Pe) .

     [Step 2] Eliminationdispersal loop: l = l +1
     [Step 3] Reproduction loop: k = k + 1
     [Step 4] Chemotaxis loop: M = M +1

     1. For i=1to S; consider bacteria steps (chemotactic) as given below

     2. Calculate weight of fitness function J (i, j, k, l). Assume M(i, j, k, l)=M(i, j, k, l) + Mcc(i(j, k, l),P(j,

     Value of J parameter indicates fitness of solution, sort solution J parameter and C(i) parameter in ascending.

     b) Sr =S/2 solution (bacteria) with poor health Jhealth dies. Balance solution ( bacteria) split into two bacteria.this process are carried at the location of parents.

     [Step 7] return to step 3 condition k < Nre .
     [Step 8] Elimination- Dispersal // return best solution For i=1 to S apply elimination and dispersion to each solution ( bacteria) with Ped (given probability)

     // helps in maitaing population size )

     return to step 1 If l < Ned .

3. PROPOSED WORK

   • Problem Definition

     In our work we consider circular coverage pattern with radius r as a range for all mobile sensors. Area covered for sensing is r 2 for each sensor. Set of mobile sensors n is given by S = {S1, S2.., Sn} and each deployed at

     location having coordinates (xi, yi). The fitness value of

     deployment is the overlapping amongst the deployed mobile sensors. This fitness value is calculated by square

     area matrix(AM)..each element of AM represents the

     A11

     A21

     A12

     A22

     A13 A1n

     A23 A2n

     overlapping among adjacent sensors e.g. A31 represents

     Area Matrix (AM) =

     A A A A

     overlapping among sensor 3 and 1.

   • Proposed Solution

     Given a set of sensors, it is desired to compute the coordinates of sensors (xi, yi), through the soft computing techniques, that minimizes the overlapping sensing range

     31

     An1

     32 33

     An 2 An3

     3n

     Ann

     and maximizes the coverage of area A.

   • Mathematical Model

   In this model, for a two-dimensional physical space, each sensors range is considered as circle and is placed at the centre say (x, y) of such circle with radius r of the circle as the sensing range of sensor. Thus, the sensing area is r 2 , while its communication range is greater than 2r. So, in a given two-dimensional physical space of area A, the n numbers of sensors are randomly deployed in said manner.

   The coordinates of centre of circles are denoted as: (xi, yi), where i = 1,2, 3., n

   The area of overlapping between two nodes i and j is

   . (1)

   represented by Aij and is calculated by

4. RESULTS & EXPERIMENTS

   We have performed the experiments by using soft computing algorithms such as GA and BFO algorithms. These algorithms perform on the principal to find out best optimum solution to a given problem. Genetic algorithm computes best solution by using Crossover and mutation provinces. Bacterial Forging optimization approach use three operators chemotactic steps, reproduction and elimination-dispersal to find best optimum solution in a single iteration. The parameter considered for simulation for GA and BFO are placed below in table 1 and table 2 respectively.

   Parameters	Values
   Number of rounds	10
   Crossover probability	0.87
   Mutation probability	0.13

   Table 1: Simulation Parameter (GA)

   Aij = 2r

   2

   cos

   2

   4r d 2

   1 dij

   dij

   2r

   2

   ij

   Where, dij represents distance between mobile node (i) and node (j) and given by

   Table 2: Simulation Parameter (BFO)

   dij =

   x x 2 + y

   y 2

   Parameters	Values
   Number of rounds	12
   Search space dimension (p1 & p2)	15
   bacteria (s) quantity	6
   Steps number (Nc)	10
   Swims boundaries (Ns); limit length	6
   Steps for reproduction number (Nre)	6
   Events count (Ned) for elim/disp.	2
   Probability (Ped) of elim/disp.	0.25

   ….. (2)

   i

   i

   j

   j

   1 n n

   Total Overlapping of Deployment =

   2 Aij (3)

   i=1 j=1

   For example, the area of overlying between two nodes, say p and q, is given by

   Both these approaches are validated by simulation them in

   2 1 dpq

   dpq

   2

   2

   MATLAB using core i7@2.50 GHz processor with 8 GB

   Apq = 2r cos

   4r d

   pq

   .. (4)

   RAM based computer running on Windows 7 platform.

   2r 2

   Amount of overlapping among two adjacent node is calculated and placed in a square matrix of order n which is shown as under :

   Both the approaches were simulated with the simulation parameter given the table 1 and table 2. Two network scenario simulated by these two approaches are mentioned in table 3

   Table 3: Network Parameters

   Scenario No.	Iteration	Sensors	Radius	Area of Deployment
   1	2000	70	7m	100X100 m
   2	2000	70	14m	200X200m

   In order to compare the performance the average covered area by GA and BFO approach for 2000 iterations were recorded .Twenty five trails were carried out for each approach and results are placed in table 4

   Table 4: Performance comparison of GA and BFO

   Scenario No	GA Covered Area	BFO Covered Area
   1	94.3760	95.3427
   2	94.9204	95.2446

   Scenario	Algorithm	Minimum	Average	Maximum
   1	GA	93.2014	94.3760	95.9955
   	BFO	94.1520	95.3427	96.4155
   2	GA	93.8968	94.9204	96.7792
   	BFO	94.4566	95.2446	96.3279

5. CONCLUSION

Wireless Sensor Network is utilized to sense the accurate observations from harsh environments. The network is deployed to sense the information from a particular defined area. To enhance the network coverage optimum positions of the nodes are to be determined. This problem reduced to NP hard problem in which the overlapping area amongst snsor is to be minimized. In the purposed work two deployment approaches were proposed based on Genetic Algorithm and Bacterial Forging Optimization algorithm. Genetic algorithm use crossover and mutation operators for generation of new Childs and on the basis of best fitness select the nodes. Bacterial Forging Optimization Technique utilize different chemotactic steps, reproduction and elimination-dispersal operators to compute best optimum solution.

These approaches are validated by simulation them in MATLAB using core i7@2.50 GHz processor with 8 GB RAM based computer running on Windows 7 platform. The average covered area by applying both approaches for two network scenarios for 25 trails were recorded. It is observed from the simulation results of table 4 that BFO approach provides better coverage as compared to GA approach. Conclusion could be drawn from the results that BFO approach could be used to find optimal sensor deployment in large target area having harsh environmental conditions

REFERENCES:

1. Jie Jia, Jian Chen, Guiran Chang, and Zhenhua Tan, Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm, Computers and Mathematics with Applications, Vol. 57, pp. 1756-1766, 2009.

2. A. Zahmatkesh and M. H. Yaghmaee, A Genetic Algorithm- Based Approach for Energy-Efficient Clustering of Wireless Sensor Networks, International Journal of Information and Electronics Engineering, Vol. 2, No. 2, March 2012.

3. Shiyuan Jin, Ming Zhou, Annie S. Wu, Sensor Network Optimization Using a Genetic Algorithm, School of EECS, University of Central Florida Orlando, FL 32816.

4. Yang SUN, and Jingwen TIAN, WSN Path Optimization Based on Fusion of Improved Ant Colony Algorithm and Genetic Algorithm, Journal of Computational Information Systems, Vol. 6, Issue 5, pp. 1591-1599, 2012.

5. S.M. Hosseinirad, and S.K. Basu, Wireless sensor network design through genetic algorithm, Journal of AI and Data Mining Vol. 2, No. 1, pp. 85-96, 2014.

6. Mohammad M. Shurman, Mamoun F. Al-Mistarihi, Amr N. Mohammad, Khalid A. Darabkh, and Ahmad A. Ababnah, Hierarchical Clustering Using Genetic Algorithm in Wireless Sensor Networks, MIPRO 2013, May 20-24, 2013, Opatija, Croatia.

7. Amol P. Bhondekar, Renu Vig, C Ghanshyam, Madan Lal Singla, and Pawan Kapur, Genetic Algorithm Based Node Placement Methodology for Wireless Sensor Networks, Proceedings of the International Multi Conference of Engineers and Computer Scientists, Vol. 1, pp. 1820, March, 2009, Hong Kong.

8. Shiyuan Jin, Ming Zhou, Annie S. Wu, Sensor Network Optimization Using a Genetic Algorithm, School of EECS, University of Central Florida Orlando, FL 32816.

9. Naeim Rahmani, Farhad Nematy, Amir Masoud Rahmani, Mehdi Hosseinzadeh, Node Placement for Maximum Coverage Based on Voronoi Diagram Using Genetic Algorithm in Wireless Sensor Networks, Australian Journal of Basic and Applied Sciences, Vol. 5, Issue 12, pp. 3221- 3232, 2011.

10. Seyed Mahdi Jameii and Seyed Mohsen Jameii, Multi- Objective Energy Efficient Optimization Algorithm for Coverage Control in Wireless Sensor Networks, International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol. 3, No.4, August 2013.

11. Omar Banimelhem, Moad Mowafi, and Walid Aljoby, Genetic Algorithm Based Node Deployment in Hybrid Wireless Sensor Networks, Communications and Network, Vol. 5, pp. 273-279, November 2013.

12. Yingyou Wen, Jie Jia, Jian Chen, Guiran Chang, and Jingping Song, Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius, Computers and Mathematics with Applications Vol. 57, pp. 1767-1775, 2009.

13. Yong-Hyuk Kim and Yourim Yoon, Efficient Genetic Algorithm for Maximum Coverage Deployment in Wireless Sensor Networks, IEEE Transactions on Cybernetics, Vol. 43, No. 5.

14. Mohamed Younis and Kemal Akkaya, Strategies and techniques for node placement in wireless sensor networks: A survey, Ad hoc Networks, Vol. 6, pp. 621-655, 2008.

15. Passino KM, Biomimicry of Bacterial Foraging, IEEE Control System Magazine, Vol. 22, pp. 52-67, 2002.

16. Dang, J., et al.: Option model calibration using a bacterial foraging optimization algorithm. In: Giacobini, M., et al. (eds.) Evo Workshops 2008. LNCS, Vol. 4974, pp. 133143. Springer, Heidelberg 2008.

17. Das, S., Biswas, A., Dasgupta, S. and Abraham, A. Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications, Vol. 203 of Studies in Computational Intelligence, Springer Berlin/Heidelberg, pp. 2355, 2009.

18. Hossain, A., Biswas, P.K.; Chakrabarti, S., Sensing Models and Its Impact on Network Coverage in Wireless Sensor Network, industrial and Information Systems, IEEE Region 10 and the Third international Conference on, Kharagpur, pp. 1-5, 2008.

19. Uribe, C., Grote, W., Radio Communication Model for Underwater WSN, New Technologies, Mobility and Security (NTMS), 2009 3rd International Conference on, Cairo, pp. 15.

20. J. Yick, B. Mukherjee, and D. Ghosal., Wireless sensor network survey Computer Networks, Vol. 52, Issue 12, 2008.

21. S. Devi, M. Geethanjali, Application of Modified Bacterial Foraging Optimization algorithm for optimal placement and sizing of Distributed Generation, Expert Systems with Applications, Vol. 41, Issue 6, pp. 2772-2781.

22. J. Doyne FARMER and Norman H. PACKARD, Alan S. PERELSON, The Immune System, Adaptation, And Machine Learning, Physical 22D, pp. 187-204 North- Holland, Amsterdam.

23. Livjeet Kaur, Mohinder Pal Joshi, Analysis of Chemotaxis in Bacterial Foraging Optimization Algorithm International Journal of Computer Applications, Vol. 46, No. 4, 2012.

24. Mary Saranya, Rajapandiyan A, Fathima K., Hema S, GeethaPriya S, Saravanan S, A Power System Stabilizer for Multi-Machine Power Based on Hybrid BF0A-PSO, International Journal of Electrical and Computer Engineering, Vol. 5, No. 2, pp. 213-220.

25. Dac-Nhuong Le, GA and ACO Algorithms Applied to Optimizing Location of Controllers in Wireless Networks, Vol. 3, No. 2, pp. 221-229.