Journal of Green Engineering

Vol: 4    Issue: 3

Published In:   April 2014

Prolonging the Lifetime of the Wireless Sensor Network Based on Blending of Genetic Algorithm and Ant Colony Optimization

Article No: 5    Page: 245-260    doi: 10.13052/jge1904-4720.435    

Read other article:
1 2 3 4 5

Prolonging the Lifetime of the Wireless Sensor Network Based on Blending of Genetic Algorithm and Ant Colony Optimization

Received 21 January 2015; Accepted 12 February 2015; Publication 19 March 2015

Soumitra Das and Sanjeev Wagh

  • Dept. of Computer Engineering, Sathyabama University, Chennai, India
    Dept. of Computer Engineering, KJ College of Engineering and Management Research, Pune, India
    Corresponding author: Soumitra Das <soumitra_das@yahoo.com>


Abstract

The application of WSN has developed manifolds in the last few years. The lifetime of a sensor node is mainly focused around the battery fuelled gadgets. There are numerous strategies to save energy and one of the best viable techniques of saving energy was discovery of the multipath shortest route from source to destination for both data dissemination and data aggregation. In this paper, we propose a hybrid model for energy optimization focused on formation of Cluster and Cluster Head determination based on Genetic Algorithm. And then apply an Ant Colony Optimization algorithm to find the shortest path from source Cluster Head to destination Sink using multipath routing data transmission. This will help to obtain reliable communication in case of node failure by means of route refurbish mechanism. The fundamental objective is to retain maximum lifetime of the network throughout the data transmission phase in a proficient manner. The proposed algorithm was compared with Genetic Algorithm Based Energy Efficient Clusters [5] and Energy Efficiency Performance Improvements for Ant-Based Routing Algorithm [12] for energy efficiency. The effectiveness of the proposed algorithm is demonstrated by simulations.



Keywords

  • ACO
  • Clustering
  • Data Aggregation
  • Energy Efficient Routing
  • EEABR
  • GABEEC
  • GA
  • WSN

1 Introduction

Modern advancements in engineering, science and communication have motivated the development of low cost, low power, and tiny wireless sensor communication devices. However, the most challenging issue is the insufficient battery power of the sensor nodes. Designing of Wireless Sensor Network (WSN) algorithms needs to focus on the parameters to amplify the life span of the sensor nodes and in turn the entire network. Performance issues related to energy consumption are evaluated by Ehsan et al. [1]. Cluster based routing and data aggregation methods are the most admired techniques in WSNs for energy efficiency [2]. These research studies have demonstrated blending of, two research methods, Genetic Algorithm (GA) and Ant Colony Optimization (ACO) to reap the synergistic benefits in order to boost the energy efficiency of the sensor nodes. The proposed algorithm executes as follows:

  1. Selection of Cluster Head (CH) and formation of clusters using GA.
  2. Shortest path selection based on ACO algorithm.
  3. Failure detection using Route Refurbish Mechanism and best shortest path selection using ACO for rerouting.

Section 2 related work briefly examines the existing work of GA and ACO protocols. Section 3 describes the proposed work, Section 4 illustrates the implementation and results. The need of future research and validation has been mentioned in the conclusion section.

2 Related Work

This section is divided in two parts and describes various methods of energy efficient routing algorithms. The first part focuses on GA based energy efficient selection of (CH) and forming of clusters and the second part explains about energy efficient ACO based shortest path discovery from source to the destination node.

2.1 GA based CH Selection and Cluster Formation Approaches

The demonstration of GA was first derived from Darwins theory of evolution [3]. Darwin suggested that the individual who is the fittest will continue to exist in the context of survival [4] [13] and others will eventually perish. Similar theory has been used by GA based CH selection. Here also, a fittest entity is considered to be the candidate for CH selection.

In one of the published article, [5], Selim et al. has projected a cluster based method which is comparable to Low Enery Adaptive Clustering Hierarchy (LEACH) and works in two phases: set-up phase and steady-state phase. In the set-up phase, predefined set of sensor nodes are chosen as CHs. Number of CHs and clusters are same as only one CH is related to each cluster. The member nodes opt to join nearest CH based on the distances. In the steady-state phase, all the nodes actually start the process of communicating with the CHs using the Time Division Multiple Access (TDMA) schedule. To complete a single round, the Cluster Head collects the data from the member nodes, fuses it, and packs the data into a single packet and sends to the Base Station (BS). After every round, energy of each CH is checked and if found fewer than the average energy of all the associate nodes, a new CH is selected based on the node that has the maximum residual energy and the old CH then becomes an associate node. Chromosomes stand for the network where CH is represented using 1 and associate node is represented using 0. Randomly the initial population is generated. The fitness of every node is calculated and based upon the fitness, the fittest chromosome is selected for applying crossover and mutation. The author has considered three parameters for selection of the fitness function. The parameters are Cluster distance C, which is the sum of distances from associate nodes of the CH and then from CH to the BS, the round at which the first node dies (Rfnd), and the round at which the last node dies (Rlnd).

The fitness function (F) is defined as

F=i(fi*ωi)fi(Rfnd,Rlnd,C)(1)

Thus, the projected protocol is better than the classical LEACH in terms of the number of alive nodes. Even though, it resulted in improvement of lifetime of the network along with achievement of energy efficient cluster formation and CH selection, it failed to change the clusters throughout the lifetime of the network. Also, only the CHs are rotated every time resulting into lack of efficiency and throughput of the network.

Furthermore, in their paper [6], Abbas et al. has proposed a method where in the fitness function calculation depends upon difference of energy of chromosomes in the current and the previous round. Chromosome with least difference gets selected. The proposed algorithm initializes the network, and eventually each and every sensor node sends its positions to its corresponding neighbour nodes. It calculates the fuzzy parameter ‘Chance’ by considering fuzzy descriptors such as energy, density and the centrality of the nodes. The nodes that have the higher ‘Chance’ than their neighbours will be selected as the candidate for CHs. The BS applies a GA based on chaotic and selects the CHs from the candidates pool list and then the new CH broadcasts to the network and the member nodes which are nearest to the CH will then join and form clusters. This proposed method is successful in increasing the lifetime of the network. The only disadvantage is that while calculating the fitness, only energy is taken into account. The implied hypothesis is that if the distance was considered, the results may have been better.

In this paper [4], Sanjeev et al. has projected a GA for optimizing the sensor nodes energy consumption with clustering techniques. A multi-objective algorithm enabled generation of an optimal number of sensors-clusters with CHs. This approach reduced the expenditure of transmission. The author has used the theory of multi-objective to reduce energy utilization and maximizing the coverage area in the WSN by considering the regular genetic process, linear ranking technique along with selection pressure. The fitness for every sensor node is calculated using ratio of Minskowsk’s distance between all solution pairs in the normalized objective space and the niche count for each solution. The authors inferred that the line of attack involves a new means for cluster formation which ultimately lengthens the lifetime of the network through equally distributed clustering.

2.2 ACO for Shortest Path Selection Approaches

ACO based energy efficient routing protocols have the ability to select the shortest path among the possible paths from the source to destination.

In this particular literature [7], Camilo et al. has shown a better version of the ant based routing in WSN, the Energy Efficiency Performance Improvements for Ant-Based Routing Algorithm (EEABR). This method considers the nodes in terms of energy level and distance of the path navigated by the ants.

The recommendation of the authors was that in the basic ant algorithm, the forward ants are propelled to no explicit target node. This indicates that sensor nodes need to converse with each other and also, the routing tables of each node should hold the identification of all the sensor nodes in the neighbourhood and the succeeding stages of pheromone trail. In their work, success was recorded in energy savings to a great extent, but encountered ambiguity in the mobility and dynamic setting as lot of control traffic was produced hence consuming a lot of energy reducing reliability.

In this paper [8], Liu et al. has projected a routing method, taking into account the ACO based algorithm. The ant uses the routing mechanism based on the angle of deflection, energy and distance as routing aspects. Although the convergence rate of this particular algorithm is admirable, the algorithm fails to make use of redundancy of data. Thus, the disadvantage is the data correlation. However, the energy expenditure of the communication is vast when a lot of sources are present in the network.

In this paper [9], Ren et al. has projected a multipath routing protocol based on ant colony system, which extends the network life span. Even though the algorithm balances the energy utilization among nodes by multipath, it does not take into consideration the influence of the minimum energy node on multiple paths.

The authors of this paper [10], Nikolidakis et al. have demonstrated a new protocol called equalized CH election routing. This protocol pursues energy saving through balanced clustering. Energy efficient routing in WSNs through balanced clustering algorithm models the network as a linear system using the Gaussian elimination algorithm. It then calculates the mixture of nodes that are probable CHs in order to amplify the network life span. This protocol is definitely proficient in terms of network life span when evaluated against other well known protocols.

3 The Proposed Approach

The operation of the proposed approach is alienated in three stages to do the entire mission of sending the desired data to the sink through CH. The proposed three phases: phase 1, the selection of CH and formation of clusters using GA, phase 2, ACO algorithm for finding and selection of shortest path and the final phase 3, will be responsible for routing using route refurbish mechanism. The proposed system model is shown in Figure 1.

images

Figure 1 Proposed system model.

3.1 Cluster Formation Using GA

The objective of the cluster formation is to prolong the network lifetime by means of clustering along with maximizing the working time of the cluster and minimizing the energy consumption in the cluster. The conventional hierarchical clustering algorithm does not provide accurate formation of clusters and selection of CHs. If the cluster is reconstructed every time, then it will unnecessarily use energy reducing the data aggregation efficiency.

In order to overcome this, our phase 1 adopts a GA based dynamic clustering technique. GA first finds the optimum number of CHs based on residual energy, radio frequency signal strength and centrality of the nodes. Once the CH is chosen, then each member sensor node will join the nearest CH based on the Euclidean distance between CH and the member node. For a cluster with ‘m’ static member nodes, cluster distance (cd) is defined as

f(cd)=i=0mdist(i,ch)(2)

Where, dist (i, ch): is the Euclidean distance between ith node and the CH. The energy function of a wireless sensor node is equivalent to the fitness function of GA based on the negligible consumed energy from network nodes in every generation. Here, it maintains a population of individuals which is called a chromosome. Every chromosome is evaluated by an utility known as fitness function. Next fresh population is generated from the current one through selection, crossover and mutation described as follows:

Selection Mechanism: The purpose is to select more healthy individuals (parents) for crossover and mutation.

Crossover: It causes swap over of the genetic materials among parents to form offspring.

Mutations: It incorporates new genetic resources in the offspring. It is possible that a regular node may become CH and a CH may become a regular node.

Finally, after crossover and mutation are over, the BS selects the chromosomes which have the networks smallest amount of energy difference in percentage of the previous round and introduces the existing nodes in the network as CH and other nodes connect to the nearest CH.

3.2 Pseudo Code for Cluster Formation

  1. Initialize the population P (t) at t = 0, where t = time.
  2. Compute the fitness P (t) based on residual energy, radio frequency signal strength and centrality.
  3. Increment t by 1.
  4. If fitness is less than the required threshold, then terminate.
  5. Select P (t) from the P (t-1) list.
  6. Crossover P (t).
  7. Mutate P (t)
  8. Repeat step 2 to 7 till all the fitness of the nodes is tested.
  9. Then the BS selects the CH based on the fitness of the node.
  10. Introduce CH to all nodes in the network.
  11. Each sensor node joins to the nearest CH based on Euclidean distance i.e. shortest distance.
  12. Each sensor node transmits data to the CH with a single hop transmission only.
  13. After all data has been received, CH aggregates all the data and then transmits it to the BS through multiple hops using ACO based shortest path algorithm.

3.3 Shortest Path Routing Based on ACO

The basic concept was derived from the ant colony where the ants are placed initially in the Source node (Sn) with the task of finding out paths through the in-network nodes to the destination node (Dn). An ant going from the Sn to Dn collects information about the quality of the path, and uses this information to update the pheromone of the best paths in the pheromone table [11].

The proposed method uses ACO algorithms to find multiple routes from Sn to Dn, after the cluster formation process is completed. As when an event occurs, the member nodes send the gathered data to the respective CH. Then, to route the data from Sn to Dn, the CH sends a route establishment message to the neighbour’s CH node. When a neighbour CH node receives the route establishment message, it checks for the next neighbour CH node and this process continues till it gets the Dn and eventually a hop tree is formed. This process is repeated multiple times from Sn to Dn to get multiple paths. Having multiple paths can maximize the network lifetime by transferring the data from Sn to Dn through the shortest path and also maximizes the reliability. The advantage is due to multiple routes because if one route fails, the data could be re-routed through the alternate route having minimum distance from Sn to Dn. The objective is to maximize the network lifetime and minimize the energy consumption of the nodes.

3.4 Pseudo Code for Shortest Route Selection

  1. Initialize the parameters
  2. Initialize array heuristic
  3. Initialize the pheromone matrix.
  4. Stop when conditions are not satisfied
  5. Build solutions
  6. Apply local search
  7. Update pheromone
  8. End
  9. View best solution
  10. Stop

3.5 Pheromone Table Update

The responsibility of the pheromone table is to maintain the information collected by the Forward Ant (FA). Every node maintains a table which records the amount of pheromone on each neighbour lane. The node has a distinct pheromone scent, and the table is in the shape of a matrix as shown in Figure 2.

images

Figure 2 Pheromone table of node A.

The rows represent the destinations and columns represent the neighbours. An entry in the pheromone table is indicated by Pn,d where ‘n’ is the neighbour index and ‘d’ stands for the destination index. The contents in the pheromone table are used to compute the selecting probabilities of every neighbour. The routing table is updated at each node by the following equation

τ(x,y)=(1ρ)*τ(x,y)+[ ΔτϕBwl ](3)

Legend Explanation
ϕ Coefficient
Bwl distance travelled by backward ant l
ρ is coefficient such that (1-ρ) represents the evaporation of pheromone trails since the last time τ (x, y), when updated

It is important to note that all neighbours are probable destinations in the route selection method of routing.

3.6 Route Refurbish Mechanism

Route maintenance plays a very significant role in WSN’s as the network keeps changing dynamically and the routes found good during discovery may turn to be bad. Possible cause of failure includes low energy, physical destruction and communication blockage. The route created to send the data toward the sink node is unique and efficient, any failure in one of its nodes cause disruption, preventing the delivery of aggregated data to the neighbour node. Our algorithm offers a route refurbish mechanism by finding the goodness of a route regularly and updates the pheromone counts for the different routes at the source nodes. To accomplish this, when a destination node receives a packet, it sends an acknowledgement message to the source informing the well being of that route.

As seen in the Figure 3 the data is routed from source node to the destination node through route 1, but when it found that the node is not responding due to failure of the node i.e. no acknowledgement is sent back to the source. The source initiates the route refurbish algorithm and selects another route based on the shortest path and data is transmitted through route 2 to the destination.

images

Figure 3 Route refurbished mechanism when route fails.

4 Implementation and Results

The proposed algorithm was simulated using MATLAB R2009b and compared with Genetic Algorithm Based Energy Efficient Clusters (GABEEC) [5] and Energy Efficiency Performance Improvements for Ant-Based Routing Algorithm (EEABR) [12]. Figure 4 and Figure 5 shows the simulation parameters along with their values.

images

Figure 4 WSN parameters.

images

Figure 5 GA parameters.

The proposed methodology has used the random deployment model for the WSN topology set-up. The BS is placed in the location (120, 50) away from the sensor field. We have compared our results with GABEEC [5] and EEABR [12] protocols. Energy is one of the major issues in wireless sensor network.

Figure 6 shows the energy consumption of network with respect to time. From Figure 7 clearly depicts that our proposed algorithm is better in terms of energy consumption by almost 72 percent as compared to other two protocols.

images

Figure 6 Energy consumption with respect to Time.

images

Figure 7 Comparison of different protocols for energy consumption.

Figure 8 presents the obtained energy value in each round with respect to the number of rounds. Also, from Figure 9 it is evident that our proposed algorithm is superior in terms of energy value (left over network energy) by 9 percent as compared to GABEEC and EEABR protocols.

images

Figure 8 Energy comparison in each round.

images

Figure 9 Comparison of different protocols for energy value.

Figure 10 shows the number of alive nodes with respect to time that is the lifetime of the network. From Figure 11, it is apparent that our proposed algorithm is also better in terms of alive nodes in the network as against the GABEEC and EEABR protocols.

images

Figure 10 Network lifetime.

images

Figure 11 Comparison of different protocols for number of alive nodes.

Figure 12 illustrates the throughput of the network. Lastly from Figure 13 it is noticeable that our proposed algorithm is an improved throughput by approximately 32 percent as compared to GABEEC and EEABR protocols.

images

Figure 12 Throughput.

images

Figure 13 Comparison of different protocols for throughput.

5 Conclusion and Future work

In this paper, a novel algorithm has been proposed based on the blending of Genetic Algorithm and Ant Colony Optimization for the dynamic formation of clusters according to the position of the nodes and Cluster Head and the types of values, it is sensing. Cluster information is broadcast to each of the nodes and routing is formed. The results of our simulation study indicate that the proposed method conserves more energy than existing established methods. In future work, the focus will be to improve the throughput and network lifetime along with addition of new parameters like packet delivery ratio, packet loss ratio and end to end delay.

6 Acknowledgement

We would like to express our gratitude to Dr. B.P. Patil and Dr. Santosh S. Sonavane for their mindful and inventive remarks, all through the readiness of the paper. Last yet not the least, all my colleagues, family members, friends and my wife Dr. Soma for their colossal support.

References

[1] Ehsan S. and Hamdaoui B. A Survey on energy efficient routing techniques with QoS assurances for wireless multimedia sensor networks. Communications Surveys Tutorials, IEEE, 14 (2): 265–278, 2012.

[2] Singh S. K, Singh M. P Singh D. K. A survey of energy efficient hierarchical cluster based routing in wireless sensor networks. International Journal of Advanced Networking and Application, 2 (02): 570–580, 2010.

[3] Jianming Zhang, Yaping Lin, Cuihong, Zhou, Jingcheng Ouyang. Optimal Model for Energy-Efficient Clustering in Wireless Sensor Networks Using Global Simulated Annealing Genetic Algorithm. International Symposium on Intelligent Information Technology Application Workshops, 2008.

[4] Sanjeev Wagh and Ramjee Prasad. Heuristic Clustering for Wireless Sensor Networks using Genetic Approach International Journal of Wireless and Mobile Networking (IJWAMN), Vol.1, No.1, 51–62, 2013

[5] Selim Bayrakli and Senol Zafer Erdogan. Genetic algorithm based energy efficient clusters (GABEEC) in wireless sensor networks The 3rd International Conferernce on Ambient Systems, Networks and Technologies, 247–254, 2012.

[6] Abbas Karimi, S. M. Abedini, Faraneh Zarafshan and S. A.R Al-Haddad. Cluster Head Selection Using Fuzzy Logic and Chaotic Based Genetic Algorithm in Wireless Sensor Network J. Basic. Appl. Sci. Res, 3 (4): 694–703, 2013.

[7] T. C. Camilo, C. Carreto, J. S. Silva and F. Boavida. An energy efficient ant based routing algorithm for wireless sensor networks, in proceedings of 5th International workshop on ant colony optimization and swarm intelligence, Brussels, Belgium, 49–59, 2006.

[8] Liu. Y, Zhu. H, Xu. K and Jia. Y. A routing strategy based on ant algorithm for WSN, In proceedings of the 3rd International Conference on natural computation, Haikou, Hainan, China, 685–689, 2007.

[9] Ren X, Liang H and Wang Y. Multipath routing based on ant colony system in wireless sensor networks In Proceedings of international conference on computer science and software engineering, Wuhan, Hubei, China, 202–205, 2008.

[10] Nikolidakis S. A, Kandris D, Vergados D. D and Douligeris C. Energy efficient routing in wireless sensor networks through balanced clustering algorithms. ddd, 29–42, 2013.

[11] Farooq M and Caro GA. Routing Protocols for next-generation networks inspired by collective behaviours of insect societies An overview. Swarm Intelligence, 101–106, 2008.

[12] Zungeru, A. M., Seng, K. P., Ang, L. M., and Chong Chia, W. Energy Efficiency Performance Improvements for Ant-Based Routing Algorithm (EEABR) in Wireless Sensor Networks. Journal of Sensors, 2013.

[13] Nivedita B Nimbalkar and Soumitra S Das. A Survey on Cluster Head Selection Techniques in Multidisciplinary Journal of Research in Engineering and Technology, Vol.1 Issue 1, 01–05, 2014.

Biographies

Image

S. Das received his Bachelor degree in Computer Engineering from North Maharashtra University, Jalgaon, Maharashtra, India and Master degree in Computer Engineering from University of Pune, Pune, Maharashtra, India. Currently, he is PhD researcher at Sathyabama University, Chennai, India. His research interest includes Computer Networks, Wireless Sensor Networks, etc. He is a members of IEEE, CSI, LMISTE, IACSIT and IAENG. He is also an active reviewer of various conferences and journals.

Image

S. Wagh received his Postdoctoral from Center for TeleInfrastruktur (CITF), Aalborg University (AAU), Denmark; PhD in Computer Science and Engineering from the SRT Marathwada University, Nanded and Master degree from University of Pune, India. He is a member of IEEE, ACM, FIETE, FIE, AND LMISTE. He is an active Steering committee member for the various International conferences and workshops; a technical program committee member and a reviewer for numerous top- quality conferences and journals in Wireless Networking and Simulation.

Abstract

Keywords

1 Introduction

2 Related Work

2.1 GA based CH Selection and Cluster Formation Approaches

2.2 ACO for Shortest Path Selection Approaches

3 The Proposed Approach

images

3.1 Cluster Formation Using GA

3.2 Pseudo Code for Cluster Formation

3.3 Shortest Path Routing Based on ACO

3.4 Pseudo Code for Shortest Route Selection

3.5 Pheromone Table Update

images

3.6 Route Refurbish Mechanism

images

images

4 Implementation and Results

images

images

images

images

images

images

images

images

images

5 Conclusion and Future work

6 Acknowledgement

References

Biographies