Nature Inspired Firefly Technique for Energy And Coverage Optimization

Nature Inspired Firefly Technique for Energy And Coverage Optimization

C. Pradeepha

M.E CSE,

Department of CSE, Builders Engineering College, Nathakaddaiyur, Kangayam, Tirupur

P. Siva Kumar

Associate Professor,

Department of CSE Builders Engineering College, Nathakaddaiyur, Kangayam, Tirupur.

AbstractIn mobile wireless sensor network, coverage and energy conservation are two prime issues. Sensor movement is required to achieve high coverage. But sensor movement is one of the main factors of energy consumption in mobile wireless sensor network. Therefore, coverage and energy conservation are correlated issues and quite difficult to achieve at the same time. In this paper, these conflicting issues are considered, using one of the latest Bio- inspired algorithms, known as Firefly Swarm Optimization algorithm. Considering the limited energy of sensors, this paper presents an Energy Efficient Multi-Parameter Reverse Firefly Swarm Optimization (EEMRFO) algorithm, to move the sensors in an energy efficient manner. Our proposed algorithm reduces redundant coverage area by moving the sensors from densely deployed areas to some predefined grid points. In this proposed algorithm, energy consumption is reduced by decreasing the number of moving sensors as well as the total distance traversed. Simulation results show that, our proposed EEMRFO algorithm reduces total energy consumption utmost 60% compared to the existing approach based on Firefly Swarm Optimization algorithm. At the same time, our proposed algorithm reduces the number of overlapped sensors significantly and achieves an effective coverage of 8089% approximately.

KeywordsDegree of overlapping, Energy consumption, Firefly swarm optimization, Sensor movement, Wireless sensor network

1. INTRODUCTION

   In the past few years, wireless sensor network (WSN) is applied in diverse application areas including business, transportation, health-care, environmental monitoring and industrial automation. A large number of sensors are deployed in the area to be monitored. Mobile sensors are more efficient to cover the region than static sensors. Since mobile sensors are deployed arbitrarily at the time of initialization, energy efficiency is one of the main concerns in this scenario. The movement of sensors towards one another ought to be in an energy economical manner. From past few years swarm intelligence has been used in diverse fields [115] including WSN intended for coverage optimization, network lifetime optimization, energy efficient routing and efficient deployment of sensor nodes. Firefly Swarm Optimization (GSO) algorithm is one of the most recent Bio- inspired heuristics for optimization problems. In this paper, based on reverse GSO approach, an energy efficient algorithm, EEMRFO is proposed for the movement of mobile sensors, where every sensor node is considered as an individual Firefly. Due to random sensor deployment, two nodes can have the same coverage area. It

   results in the redundancy of network coverage, that is wastage of the dear sensor resources. Therefore, efficient sensor movement is needed for effective coverage. In this view, mobile WSN is best than static WSN for network coverage. However, the movement of sensor nodes consumes a considerable amount of energy for which the sensor network exhausts early. In our proposed EEMRFO algorithm, an energy efficient sensor movement approach is proposed to optimize the energy consumption by reducing the number of sensor movements as well as the total distance traversed. Our proposed algorithm also reduces the number of sensors overlapped to minimize the redundancy of coverage area.

2. MOTIVATION OF OUR WORK

   Several optimization algorithms exist for mobile WSN [1 15]. Though particle swarm optimization (PSO) is very useful optimization algorithm for dynamic topology [78, 10], in PSO the dynamic neighborhood is achieved by evaluating the first k neighbors. Such a neighborhood topology is limited to computational models only and is not applicable in a realistic scenario, which is required in our proposed approach. Table 1 shows the features for which GSO algorithm is chosen as a suitable optimization algorithm for our proposed mobile WSN. GSO algorithm is based on the behavior of Firefly. Fireflys have luminescent quality called luciferin with them for which we can see cold light [1]. According to the nature of Fireflys, they always move towards their neighbors having brighter luciferin than its own. But in our approach, a sensor node is attracted towards its neighbor which has lowest battery power to maximize the coverage, which is reverse of the characteristics of the Firefly. One more difference with GSO algorithm is, in our approach it is considered that each sensor will have some memory element in it. In [4] authors have presented a GSO based sensor deployment approach for better coverage in WSN. Sensors in the search space have been considered as Firefly which maximizes the coverage of sensing field by moving the sensor nodes towards its neighbor. But in this paper, they are only concerned about the coverage, but not about the energy consumption of the

   network. No consideration is there to minimize the number of sensor movement. Firefly algorithmic program is employed in multiple-carrier coverage repair to direct robots to switch broken sensors sporadically in already deployed WSN [5].

   1. Bio-Inspired Optimization for Sensor Network Lifetime (BiO4Sel) approach has developed a swarm

      optimization based algorithm for self- organization and lifetime optimization by means of routing in WSN [6].

   2. In [7], authors consider two well known optimization problems in WSN which are Energy efficient clustering and routing for extending network lifetime. Authors present Linear/Nonlinear Programming (LP/NLP) formulations of these problems followed by two proposed algorithms which are based on PSO.

   3. In [8], an improved co-evolutionary particle swarm optimization is proposed, which provides effective coverage in mobile WSN. However, no consideration is there to minimize energy consumption of the network.

   4. In [9], authors consider the issue of sensor deployment and propose ACO algorithm based deployment strategy to prolong the network lifetime, while ensuring the complete coverage of the monitoring region. They model the sensor deployment problem as the multiple knapsack problems (MKP).Through simulation it is shown that, the network lifetime can be enhanced by increasing the energy and density of the sensor nodes which are closer to the sink.

   In WSN higher the coverage rate, higher is that the quality of service. Usually mobile sensors are more efficient to cover a region under observation. But in mobile sensor network a significant amount of energy consumption happens due to movement of the sensors which reduces the network lifetime. In mobile WSN, energy consumption mainly depends on the number of sensor movement and the traversed distance. Another issue of WSN is redundant coverage area. After random device preparation, two nodes can have the same coverage area. This results in the redundancy of network coverage.

   It may cause wastage of the dear device resources. So motivation of our work is to

   1. Reduce energy consumption due to sensor movement by decreasing the number of moving sensor nodes.

   2. Reduce energy consumption by minimizing the distance of moving sensor from the target sensor as much as possible.

   3. Reduce the number of overlapped sensors, therefore minimizing the redundancy of the coverage area./p>

3. AUTHORS CONTRIBUTION

   According to the basic GSO algorithm [1,4] every Firefly calculates a probabilistic value to select its neighboring Firefly which has a higher intensity of luciferin than its own. The Firefly decides to move towards the selected Firefly on the basis of this probability value. For each Firefly i, the probability of movement towards a neighbor k is as follows,

   f k (t )f i (t )

   and rid (t) signifies RtThIeCCvTar-ia2b01le9 CnoenifgehrebnocrehoPordoceerdaningges

   associated with Firefly i at time t.

   But in basic GSO algorithm, apart from luciferin value it does not consider any other parameters for Firefly movement. As a result, a huge amount of energy consumption happens due to sensor movement. Here every sensor node is treated as Firefly in the area under observation. Also some of the sensors will move unnecessarily though the target sensor has sufficient amount of residual energy. This happens as it does not check the threshold energy before moving. In our proposed approach, we have minimized those limitations. In this approach, reverse characteristics of Firefly is adopted for movement of sensors in the search space. Here the distance between neighboring nodes and the number of overlapped sensors are considered as parameters in time of selecting target sensor for movement. The sensor node which has the lowest battery life in the sensing region is known as the target sensor node. The contributions of our proposed approach are as follows:

   1. Reduce energy consumption

      1. By reducing the number of sensor movement: According to our algorithm, two types of sensor movement can take place for the following two purposes:

         1. To cover the lower battery target node: The sensor node i moves towards a neighbor node k which has lowest battery power, known as target sensor node. The movement will take place only if the target sensors residual energy is less than a threshold value, for which target sensor becomes unable to cover the desired sensing region.

         2. To reduce the number of overlapped sensor: The situation when no target node is there to cover, the node from densely deployed area moves towards the nearest grid points. Through this movement, it reduces the number of overlapped sensors. In our proposed algorithm, the first priority is to cover the lower battery target node in an energy efficient manner. If no target node is there to cover, the sensor movement happens for reducing overlapped region. Therefore, our algorithm approaches one of these problems at a time and reduces the number of sensor movement.

      2. By reducing the distance of moving sensor from the target sensor: In our proposed approach, the distance of moving sensor from the target sensor is minimized. Consequently energy consumption due to sensor movement is reduced as much as possible. In support of that, the node which has to traverse larger distance will have lower movement score to get selected for movement. Also to reduce the number of overlapped sensor, the highest degree of overlapping node moves towards the nearest grid point. Therefore the distance of moving is reduced.

         pik (t )

         = f j (t )f i (t )

         jGi (t )

   2. Reduce redundant coverage area

      d

      d

      Where f i (t ) represents the luciferin level associated with Firefly i at time t. Gi (t ) is the set of neighbors of Firefly i at time t and is denoted as, Gi (t ) = {k: dik (t) < ri (t); f i (t )

      < f k (t ) } and k Gi (t ) . Euclidian distance between Fireflys i and k is represented as dik (t)at time t

      Overlapping of sensors occurred due to random deployment. By decreasing the number of overlapped sensors, redundancy of the coverage area can be reduced as much as

      possible. Our proposed algorithm reduces the overlapped region in two ways:

      1. The node which has higher degree of overlapping will have higher chance to get selected for movement to cover the target sensor node. Degree of overlapping of a particular node is the number of nodes to which that particular node is overlapped having Euclidian distance less than 3 r where r is the radius of the sensor node.

      2. The algorithm also reduces the number of overlapped sensors by moving the sensors from densely deployed areas to some predefined grid points, when no target sensor node is there to cover. As a result, it extends effective coverage of the network.

   3. Efficient sensor movement

   For efficient sensor movement, the movement score of node i for moving towards a neighbor node k , consider not only the battery power of sensors but also the distance from neighborhood sensor and degree of overlapping. The move- ment score value of sensor i to move towards the target sensor

   kis calculated by Eq.(2).

   p

   bi (t )bk (t )

   bi (t )bk (t )

   ik

   ik

   degi

   degi

   Farthest

   Farthest

   ik =

   d

4. PROPOSED METHOD

   1. Assumptions

      For our proposed approach, we have made the following assumptions:

      Every sensor is considered as a Firefly and every sensor is associated with a battery.

      Sensor nodes are initialized with battery power within the range of 1 J 5 J.

      Base station has the responsibility to identify the sensor which has lowest battery life in the sensing region.

      In the beginning base station informs the sensor nodes about the grid points.

      Battery life is reduced with time due to data transmission, reception and movement of sensors.

      Degree of overlapping of a particular node is the number of nodes to which that particular node is

      bi (t )bk

      i Gk (t )

      (t ) ×((1 d )+ n )

      overlapped having Euclidian distance less than 3r, where r is the radius of the sensor node.

      Here bi (t ) and bk (t ) are the battery power of the sensor node i and k at time t, where node i belongs

      to the neighborhood range of node k at time t i.e. i

      Gk (t ).Here degi isthe degree of overlappingof i th node, nis the total number of sensors, dik is the Euclidian distance between node i and node k, and

      dFarthest is thedistance of farthest node from node k.

      Larger the value of dik , lesser the contribution of

      d

      the part (1 –

      ik ) in the movement scorevalue,

      dFarthest

      resulting into lower movement score to get selected for movement.

      The node which has higher degree of overlapping degi

      will have higher chance to get selected for

      movement. Sensornode which has the lowest battery power in the sensing region isknown as target sensor. Sensor with the highest movement score value moves towards the target sensor.

      Figure 1.Directed graph of Firefly movement of reverse GSO based proposed approach.

   2. System model

      In our proposed approach, the communication range

      r c act as one of the important parameters. Neighborhood range is bounded by 2 rc (0 < rdi 2 rc ). A Firefly i consider Firefly k as its neighbor if k is within the neighborhood range of i. In our proposed approach, a Firefly i is attracted towards Firefly k if luciferin of k is lower than

      Firefly i. The movements of Fireflys are shown in Figure

      progresses, sensor from densely deployed area moves towards

      f i (t )

      1.Suppose represents the luciferin levels of Firefly i

      the predefined grid points. As a result the overlapped area is reduced. There are 121 grid points in 100 ×100 m 2 sensing

      at time t. In figure 1 five Fireflys and their direction of movements are depicted. Each Firefly has certain sensing range, depicted as dashed circles bounding each Firefly. Each Firefly will attempt to move towards its neighbor comprised with lower intensity of luciferin. The figure shows that Firefly b will try to move towards Firefly d and c, which are the neighbor of b. The reason is both of the Fireflys d and c has

      lower luciferin value f d (t = 5 and f c (t ) = 4 compare to the luciferin value of Firefly b which is f b (t )= 8. The direction of movement of every Firefly is shown by directed lines.

   3. Degree of overlapping

   According to our assumption, degree of overlapping of a particular node is the number of nodes to which that particular node is overlapped having Euclidian distance less than 3r where r is the radius of the sensor node. Since the optimal distance between two neighboring sensor is 3rfor

   maximum coverage [4] , it is considered that if the Euclidian distance between two neighboring sensor nodes is less than

   3r, then both of the overlapped sensor nodes have degrees of over- lapping 1.

   D.Grid based sensor redeployment

   Grid based sensor deployment is an efficient approach to provide quality coverage in WSN [15]. In this paper, grid structure is followed, where the whole sensing region is divided into square sized grids as shown in figure 2.

   Figure 2.Grid based sensor deployment in WSN.

   The smallest grid cell has the size of 10 ×10 m 2 . According to our algorithm, when no target sensor node is there to cover, the sensor having highest degree of overlapping, moves towards the nearest grid points to take its position. Here the grid points act as pulling forces, which prevent the sensors from gathering together about a particular point in the sensing region. As the number of iteration

   region.

   1. Range update phase

      In our proposed algorithm, the first priority is to cover the lower battery target node as mentioned in Section 5.5. (a). If no target node is there to cover, the movement of sensor node takes place to reduce the number of overlapped sensor as mentioned in Section 5.5.(b). Therefore, according to our algorithm, range update occurs due to the following two purposes, where purpose (a) is satisfied before (b):

      1. To cover the lower battery target node:For every sensor, i Gk (t ), the movement score value is calculated by Eq. (2). The i th sensor with highest movement score value is selected to move towards the target node k. The position of the sensor i is modified after its movement to the new location. The position of the sensor will be changed through Eq. (3).

         zi (t +1) = zi (t ) +

         (

         (

         zk (t )zi (t )

         |dik 3 r| |zk (t )zi (t )| )

         Where zk (t ) and zi (t ) are the locations of k th and i th sensors at time t, r is the sensing range of a sensor. In this equation sensor i is moved towards the sensor k and its position is changed up to 3 r distance from the sensor k. Range covered by the sensor with its new location is updated here.

      2. To reduce the number of overlapped sensor:In our approach, when no target sensor node is there to cover, the node which has highest degree of overlapping moves towards the nearest predefined grid point. It reduces the number of overlapped nodes, therefore extending effective coverage gradually. Here the movement will take place if the sensor node is overlapped and it is not the already covered target node. The position of the sensor node i will be changed as follows,

         zi( t + 1 ) = zi (t ) + (G( id ) zi (t))

         WhereG (id) is the location of nearest grid point from the sensor node i at time t.

   2. Energy calculation

   In our proposed approach, sensor nodes are deployed randomly. Each sensor node contains information about their position and battery power. In this approach, base station plays an important role. Base station knows about the physical location and battery power of each and every sensor node. It has the responsibility to identify the lowest battery sensor node in the sensing region after each round. Then it transmits this information to the sensor nodes.

   Sensor nodes communicate to the base station about their current position and updated battery power after each round.

   For power consumption analysis, radio energy dissipation model is used as in [14].

   1 50 100

   E 1

   ik

   = 2 (

   mi vi2 25

   0.0314	2.0003	4.9170
   0.1009	3.1461	8.4511

   0.0314	2.0003	4.9170
   0.1009	3.1461	8.4511

   )

   Here mi is the mass and vi2 is the velocity of sensor i.

5. RESULT ANALYSIS

   1. Energy consumption

   A significant amount of totalenergy consumption is reduced in EEMRFO approach by where number of sensor nodes travel in an energy efficient manner.The total energy consumption of the proposed EEMRFO approach after 100thiteration is shown in figure 3.

   50

   100 0.1907 10.0001 21.1215

   1. Distance per iteration

      For every iteration, the distance moved by sensor node is calculated based on Euclidean distance between two sensors. From figure 4, it has been concluded that the moving distance per iteration with respect to total number of iteration in the sensing region is very less.

      Hence it is obvious that,as the number of iteration increases, the number of moving sensor decreases due to decreased amount of energy.In this case, for 35 sensor nodes randomly distributed in sensing region theperformance is measured through simulation with respect to moving distance per iteration and total distance traversed by the nodes for each iteration.Once the movement of node occurs towards the target sensor node, distance is calculated based on its new updatedposition and old location of sensor in the sensing region.

      Figure 3. Total energy consumption.

      Overall energy is consumed by decreasing the number of moving sensors towards target sensor in the sensing region with respect to movement score values.Figure 3 shows energy consumption for 35 sensor nodes in the sensing region. Hence only limited amount of energy is consumed in this proposed approach which also improves the network lifetime and throughput of mobile WSN.

      Table 1 shows the total energy consumption of different sensor nodes for iterations. Energy consumption increases as number of sensor nodes increases. Overall energy consumption is reduced here by decreasing the number of

      moving sensors towards target sensor node.

      Table 2depicts the total distance traversed by different sensor nodes in the sensing region.

      Table 2. Distance traversed by sensor nodes

      Number of Distance

      sensors traversed by sensors

      (metre)

      25 29.6256

      50

      Table 1. Energy consumption

      Number Energy consumption per of sensors iteration (Joule)

      100

      32.6454

      39.9064

   2. Effective coverage area

   The number of overlapped sensor nodes decreases as the iteration of sensor nodes increases. Figure 5 shows the number of sensor nodes having different degrees of overlapping in different number of iterations.

   Figure 5. Overlapped sensor nodes

   Degreeof overlapping of a particular node is the number of nodes to which that particular node is overlapped. Here redundancy in coverage area is decreased by reducing the overlapped sensor nodes for each iteration which ensures the quality coverage area in the sensing region.Finally, by using this proposed EEMRFO algorithm, redundancy of the coverage area is reduced insufficient measure.

6. CONCLUSION

In recent days Bio- inspired algorithms are being used in diverse fields including wireless sensor network. Firefly Swarm Optimization algorithm is one of the latest Bio- inspired heuristics for optimization problems. In this paper, an energy efficient sensor movement approach based on reverse Firefly Swarm Optimization algorithm is presented, where every sensor node is considered as an individual Firefly. The lifetime of WSN depends on the energy consumption by the sensor nodes which are mainly due to data transmission and recption. But in mobile WSN, the energy consumption for sensor movement also has an effect on network lifetime. Due to random device preparation, 2 nodes will have the constant coverage area. It results in the redundancy of network coverage, which is in fact wastage of the precious sensor resources. Our proposed algorithm reduces energy consumption for sensor movement as well as reduces redundant coverage area as much as possible. Simulation results show that our proposed approach is utmost 55-60% energy efficient than the Liaos approach. This algorithm also succeeds in maximizing the effective coverage approximately

8189%. To the best of our knowledge, for the first time, using reverse Firefly Swarm Optimization approach, our proposed algorithm attempts to optimize both the energy and coverage at a time.

References

1. Shafiq Alam and GillianDobbie (2014), Research on particle swarm optimization based clustering: a systematic review of literature and techniques, Journal of Swarm and Evolutionary Computation, Vol.17, No.2, PP.113.

2. Bhattacharjee and Bandyopadhyay (2013), Lifetime maximizing dynamic energy efficient routing protocol for multi hop wireless networks, Journal of Simulation Modelling Practice and Theory, Vol.32, No.6, PP.1529.

3. Jie Wu and Shuhui Yang (2007), Optimal movement- assisted sensor deployment and its extensions in wireless sensor networks, Journal of Simulation Modelling Practice and Theory, Vol.1, No.8, PP.383399.

4. Nor Azlina Ab Aziz and Ammar Mohemmed (2010), Particle swarm optimization for coverage maximization and energy conservation in WSN,Journal of Applications of Evolutionary Computation, Vol.5, No.3, PP.5160.

5. Senthilnath and Omkar (2011), Clustering using firefly algorithm: Performance study, Journal of Swarm and Evolutionary Computation, Vol.1, No.3, PP.164171.

6. Ru Ting Wu and Kao Li (2011), Ant colony optimization based sensor deployment protocol for wireless sensor networks, Journal of Expert Systems with Applications, Vol.38, No.4, PP.65996605.

7. Reza Akbari and Ramin Hedayatzadeha (2012), A multi- objective

   artificial beecolony algorithm, Journal of Swarm Evolution Computation, Vol.2, No.4, PP.3952.

8. Krishnanand and Ghose (2009), Firefly swarm optimization for simultaneouscapture of multiple local optima of multimodal functions, Journal of Swarm Intelligence, Vol.3, No.2, PP.87-124.

9. Sudip Misra and Manikonda Pavan Kumar (2011), Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks, Journal of Computer Communication, Vol.4, No.12, PP.1484 1496.

10. Wen Hwa Liao and Yucheng Kao Li (2011), A sensor deployment approach using Firefly swarm optimization algorithm in wireless sensor networks, Journal of Expert Systems with Applications, Vol.38, No.10, PP.12180 12188.

11. A. Ray , D. De , Energy efficient clustering algorithm for multi-hop green wireless sensor network using gateway node, Adv. Sci., Eng. Med. 5 (11) (2013) 11991204 .

12. A. Ray , D. De , Energy efficient cluster head selection in wireless sensor network, in: Proceedings of IEEE International Conference on Recent Advances in Information Technology (RAIT), March 1517, 2012, pp. 306311 .

13. S. Alam , G. Dobbie , Y.S. Koh , P. Riddle , S.U. Rehman , Research on particle swarm optimization based clustering: a systematic review of literature and techniques, Swarm Evolut. Comput. 17 (2014) 113 .

14. M. Saleem , G.A. Di Caro , M. Farooq , Swarm intelligence based routing protocol for wireless sensor networks: Survey and future directions, Inf. Sci. 181 (20) (2011) 45974624 .

15. K. Xu , G. Takahara , H. Hassanein , On the robustness of grid-based deployment in wireless sensor networks, in: Proceedings of International Wireless Communications and Mobile Computing Conference, 2006, pp. 1183 1188.