Energy Optimized Routing in Wireless Sensor Networks

Energy Optimized Routing in Wireless Sensor Networks

K. Sindhu Parvathi

Department of ECE SSN College of Engineering

Chennai, India-603110

Dr. R. Amutha Department of ECE

SSN College of Engineering Chennai, India-603110

AbstractIn energy-constrained Wireless Sensor Networks, an energy efficient, multi-hop routing scheme is essential for prolonging network lifetime. Ant Colony Optimization is implemented over clustering algorithm for multi-hop routing in sensor networks. This reduces amount of direct transmissions from cluster heads to base station. The technique work in three phases: clustering, intra-cluster communication, inter-cluster communication. Cluster members send data directly to their cluster head. Ant Colony Optimization algorithm is used for communication between cluster-heads and base-station. It tends to search shortest and energy efficient route. The simulation results show that Ant Colony Optimization is an effective way of reducing average energy consumption of sensor nodes and prolonging network lifetime.

KeywordsAnt Colony optimization, clustering, multi-hop routing, Wireless Sensor Networks.

1. INTRODUCTION

   A sensor network is composed of numbers of sensor nodes, which are scattered randomly in some region. A sensor is a device that maps a physical quantity from the environment to a quantitative measurement. Sensor nodes are equipped with a sensor module capable of sensing some quantity in the environment, a digital processor for processing the signals from the sensor, a radio module for communication, and a battery to provide energy for the operation. With the sensing parts imbedded in the nodes, a Wireless Sensor Network (WSN) can monitor and gather information or data within the deployed area. A survey on WSN which are a class of wireless ad-hoc networks that contain hundreds or thousands of sensor nodes is presented in [1]. Each node has the ability to sense elements of its environment, perform simple computations, and communicate either among its peers or directly to an external Base Station (BS). Clustering techniques can considerably reduce the energy consumption [2]. Sensor nodes have limited computing power and cannot run sophisticated network protocols. Among different routing protocols to be used in WSN, clustering is a method that has commonly been found [3]. Clustering is a process of dividing a network into non-overlapping groups of sensor nodes. Each cluster is managed by a chosen Cluster-Head (CH). Cluster members send data packets to their cluster head which in turn aggregated the data packets and send them to the BS. Various design issues in clustering approach, routing protocol, increasing of the network lifetime and their relative analysis are discussed in [4]. Numerous challenging issues that influence design of routing techniques in WSNs, and

   categorized routing algorithm with comparative analysis are performed in [5]. The three important advantages of clustering process for WSN are less overheads, scalability and easy maintenance. Various energy- efficient routing algorithms for increasing the lifetime of WSN are extensively studied in [6].

2. RELATED WORK

   A survey on routing protocols in WSNs is presented in [7]. It presents a fine number of energy efficient routing protocols which have been established for WSNs. Challenges in routing algorithms are presented and design issues are also mentioned. PEACH (Power-Efficient and Adaptive Clustering Hierarchy), a clustering protocol which maximizes the network lifetime of WSN is proposed in [8]. Clustering protocols enable sensor nodes to reduce the number of transmissions by data aggregation thereby decrease the communication cost in WSN. It also improves the lifetime and energy consumption of sensor networks. PEACH has no overhead on cluster head selection and forms adaptive multi- level clustering as compared to the existing clustering protocols. Energy efficient routing for large cluster based WSNs is essential for more effective operation [9]. Because of limited energy supply, maximization of the lifetime of a WSN is a critical issue.

   In this work, we use clustering as the base for our algorithm. To further improve the routing algorithm, we use ACO to find the optimal route from the cluster heads to the base station which is discussed in [10]. Firstly, intra cluster communication takes place where the sensor nodes inside the cluster transmit their packets immediately to the cluster head. Next, ant-based system is used for the inter-cluster communication among the cluster heads to discover the optimum path to the sink node. ACO is an iterative algorithm. A number of artificial ants are considered for each iteration. After ants have built their tours, each ant deposits pheromone to form pheromone trails. Usually, each ant chooses the route with more pheromone with a greater probability. In the foraging process, after ants release pheromone, parts of pheromone will evaporate with time lapse. With this mechanism, the shorter the route generated by an ant, the greater the amount of pheromone it deposits on the paths which is presented in [12]. Thus, the short route receives more pheromone than the long ones. The local pheromone update is performed by all the ants after each construction step. The global pheromone update is applied at the end of every iteration by only one ant, which can be either

   the iteration-best or the best-so-far. The rest of the paper is organized as follows. In Section III, the proposed cluster- based ant colony optimization algorithm is presented. The results are discussed in Section IV. Finally, the conclusions are given in Section V.

3. ACO BASED ROUTING IN WSN

   Routing is one of the major problems in the WSN. Routing has been defined as a dynamic optimization task aiming at providing paths that are optimal in terms of some criteria

   ACO is discussed in detail.

   1. Construct solutions

      In ACO, after the wireless sensor network is created, each ant starts from the source node. When the source node sends the data packets, the selected probability of each adjacent node may be calculated according to the pheromone concentration of the path between the adjacent nodes in the routing tables. The formula (1) below is the probability transition rule.

      i

      i

      [ (t)] [ ]

      i

      i

      such as minimum distance, maximum bandwidth, and

      pk (t) ij ij

      if j Nk

      shortest delay. ACO is applied to WSNs routing problem. Ant colony optimization belongs to the group of meta- heuristic methods which is discussed in detail [13]. The routing process in WSN is carried out as follows.

      ij

      where,

      lNk [il

      (t)] (1[)il ]

      1. A random network of area 500*500 square meter is considered. Initially 100 nodes are placed randomly in the specified area.

      2. Cluster heads are elected and clusters are built around the cluster heads.

      3. Determine whether the source node is closer to cluster head or base station. If the source node is closer to the base station, then the data is sent to the base station directly.

      4. If the source node is closer to the cluster head, then it sends the data to its own cluster head. The information received and processed by the cluster head is then transmitted to base station thereby reducing the energy consumption.

      5. When the cluster head is far away from the base station, the single-hop communication will increase the energy consumption hence multi-hop communication is adopted among these clusters.

      6. Now, optimum path towads BS is formed by energy efficient routing algorithm.

         For practical use of ACO, it is necessary to project virtual ants. It is important to set their properties which are mentioned in [14], [15] and [16]. These properties help virtual ants to scan the network and find the shortest tour. The traversed path is saved in ant memory. In the next tour, the ant decides on the base of pheromones power. Because of the property of pheromone evaporation, pheromones on shortest edges are stronger. ACO algorithm includes two procedures namely pheromone trail evaporation and daemon actions.

         ij 1

         d

         d

         ij

         k

         k

         It is a priori available heuristic information. and are the two parameters which determine the relative influence of pheromone trail and heuristic information, and Ni is the feasible neighborhood of ant k , that is, the set of nodes (cluster heads) which the ant k has not yet visited. Parameters and have the following influence on the algorithm behaviour. If = 0, the selection probabilities are proportional to [ij] and the closest CH will more likely be selected, in this case ACO corresponds to a classical stochastic greedy algorithm (with multiple starting points since ants are initially randomly distributed among the nodes). If = 0, only pheromone information is considered, this will lead to the rapid emergence of a stagnation situation with the corresponding generation of tours which are strongly suboptimal. The solution construction ends after each ant has completed a tour, that is, after each ant has constructed a sequence of length n, where n is the number of cluster heads.

   2. Update Pheromone trails

   m

   m

   Next, the pheromone trails are updated using (2) and (3). In ACO, this is done by first lowering the pheromone trails by a constant factor (this is pheromone evaporation) and then allowing each ant to deposit pheromone on the paths that belong to its tour.

   Pheromone evaporation is the process by means of which the

   (t 1) (1 )

   (t)

   k (t)

   (i,j)

   pheromone trail intensity on the components decreases over time which have been studied extensively in [17] and [18]. From a practical point of view, pheromone evaporation is needed to avoid a too rapid convergence of the algorithm

   ij ij

   1

   k (t) Lk (t)

   ij

   k1

   if path (i,j) is used by ant 'k'

   (2)

   (3)

   towards a sub-optimal region. Daemon actions can be used to implement centralized actions which cannot be performed by single ants. First, we set the initial parameters. Then the ant

   ij

   0

   0

   otherwise

   agents are placed on the source node. In this paper, we discuss that the data packets are sent from the one source node to the one sink node. At each iteration, each ant constructs a solution and then updates the pheromone. Until termination condition met, we will get the best solution in a period searching time. In the following, the main process about constructing solutions and updating pheromone trails of

   The parameter is used to avoid unlimited accumulation of the pheromone trails and enables the algorithm to eliminate the unused path. On paths which are not chosen by the ants, the associated pheromone strength will decrease exponentially with the number of iterations. ijk(t) is the amount of pheromone the ant k deposits on the paths it had

   traversed. Lk(t) is the length of the ant's tour. The shorter the ant's tour is, the more pheromone is received by paths belonging to that tour. In general, paths which are used by many ants and which are contained in shorter tours will receive more pheromone and therefore these paths are more likely to be chosen in future iterations of the algorithm. Thus ACO algorithm converges to a single optimum path finally.

4. RESULTS AND DISCUSSION

Many techniques have been introduced in literature to reduce the amount of battery power consumed by each node in the network. Energy Efficient routing algorithms has been proved to be a better technique in terms of power consumption and efficiency. The reference network used in our simulation has 100 nodes. The sensor nodes are distributed randomly in 500*500 square meter region which is shown in Fig. 1. Each node had 0.5 joules of initial energy. The packet size was 4000 bits and five percent of the nodes were selected as cluster heads. The single sink node is located at coordinates (100,100). Since direct transmission of data from source node to base station consumes more energy, multi-hop relaying among cluster heads can be adopted. The network is divided into a set of clusters and data transmission takes place via cluster-heads through multi-hop to the sink which results in energy conservation and increase in network lifetime.

Sensor nodes are deployed over the network either in random or deterministic fashion. Network is subjected to strict energy constraints. The Simulation tool used for analysis is MATLAB. All sensor nodes might not reach the base station in single-hop, hence other nodes might need to forward information towards the base station, i.e. multi-hop. Here we use cluster heads to forward information.

1. Formation of a Clustered WSN

   Grouping of sensor nodes into a number of clusters is performed in order to achieve high energy efficiency and prolonged network lifetime. Cluster Heads are elected such that they are far away from each other and then clusters are formed around each cluster head which is shown in Fig. 2.

   Fig. 1. Random Deployment of nodes

   Fig. 2. Formation of Clustered Network

   The sensor nodes periodically transmit their data to the corresponding CH nodes. The CH nodes aggregate the data (thus decreasing the total number of transmissions) and transmit them to BS either directly or through the intermediate communication with other CH nodes.

   No. of cluster heads : 5% of no. of nodes. No. of clusters 5

   To increase energy efficiency it is important to decide the number of cluster heads that are most suitable. Large numbers of sensing nodes may congest the network with information. To solve this problem, some sensors, such as the cluster heads, can aggregate data and then send the new information towards the base station.

2. Finding Optimum routing path using ACO

   ACO algorithm is applied for only inter-cluster routing [19]. The source node transmits the data directly to its respective cluster head and then the data from cluster head to destination is routed through the optimum path which is obtained by ACO algorithm.

   Step:1 Random placement of ants in the network

   The artificial agents (ants) are randomly placed in the network. Number of ants is set to 6 in this case. In the initial stage, ants move randomly to reach the destination thus forming tours. Here CH1, CH2, CH3, CH4, CH5, D are designated as 1, 2, 3, 4, 5, 6 respectively.

   Tour 1:	4	6	1	5	3	2	4
   Tour 2:	6	1	3	5	4	2	6
   Tour 3:	6	3	2	5	4	1	6
   Tour 4:	4	5	2	1	3	6	4
   Tour 5:	1	2	3	5	4	6	1
   Tour 6:	4	1	2	6	3	5	4

   Step 2: Construction of solution

   The tours are rearranged by probability transiion rule using (1). It is based on the paths having shortest Euclidean

   distance and more pheromone concentration and then length of each tour is determined which is shown in Table I.

   TABLE I. LOCAL UPDATED TOUR (ITERATION 1)

   S.NO	ARRANGEMENT OF TOURS							LENGTH OF THE TOUR (m)
   1	4	5	6	2	3	1	4	1791.4
   2	6	2	5	3	4	1	6	1915.1
   3	6	2	5	3	1	4	6	1628
   4	4	6	2	3	5	1	4	1668.8
   5	1	4	6	2	5	3	1	1628
   6	4	6	2	5	1	3	4	1869.6

   It is a compromise between

   • Visibility () that prefer closer nodes than distant ones.

   • Intensity of Pheromone () that prefer most frequently used paths.

     Step 3: Pheromone updation

     Deposition of pheromones (on the frequently used paths) and evaporation of pheromones (on unused paths) takes place in this phase using (2) and (3). The pheromone concentrations on all the paths at the end of iteration 1 are tabulated in Table

     II. The pheromone values are initialized to a constant value (0.1) for 1st iteration. Pheromone starts to accumulate faster on the shortest tour which will eventually be used by majority of the ants. This is done by first lowering the pheromone trails by a constant factor (this is pheromone evaporation) and then allowing each ant to deposit pheromone on the paths that belong to shortest tour. On paths which are not chosen by the ants, the associated pheromone strength will decrease exponentially with the number of iterations. The paths which are used by many ants will receive more pheromone and therefore that particular path is more likely to be chosen in future iterations of the algorithm. The evaporation helps to find the shortest path and provide that no other path will be assessed as the shortest. This evaporation of pheromones has an intensity .

     After much iteration (30 iterations in this case) ACO converges to a single optimum path which is the shortest of all the tours. The final updated tour at the end of iteration 30 is shown in Table III. It is found that all the ants try to follow the same optimum path finally.

     Optimum path: (4 6 2 5 3 1 4)

     TABLE II. LOCAL UPDATED PHEROMONE (ITERATION 1)

     TABLE III. GLOBAL UPDATED TOUR

     S. NO	ARRANGEMENT OF TOURS							LENGTH OF THE TOUR (m)
     1	4	6	2	5	3	1	4	1628
     2	6	2	5	3	1	4	6	1628
     3	6	2	5	3	1	4	6	1628
     4	4	6	2	5	3	1	4	1628
     5	1	4	6	2	5	3	1	1628
     6	4	6	2	5	3	1	4	1628

     At the end of last iteration, the pheromone concentration gets accumulated more on the optimum path whereas on unused path the pheromone concentration gets decreased. The global updated pheromones for all the paths are tabulated in Table IV.

3. Data Transmission phase

   Transmission of data from source node to CH1 is called as intra-cluster communication and transmission of data among CH1, CH4, D is called as inter-cluster communication. After finding the optimum path using ACO for inter-cluster routing, data transmission from source to destination takes place. The source node is within cluster 1. So the data is first transmitted from source node to CH1 and then it is transmitted through optimum path found by ant colony Optimization Routing Algorithm from cluster head 1 (CH1) to destination (D) which is shown in Fig. 3. After the data get transmitted from source to destination, then the energy consumption for data transmission from source to destination is analyzed.

4. Energy Consumption model

We assume a simple model for the energy dissipation of the node radio hardware given in Fig. 4. In this model, the transmitter dissipates energy to run the radio electronics (Eelec) and the power amplifier (Eamp), and the receiver dissipates energy to run the radio electronics. To transmit a k- bit message to a distance of d, the dissipated energy is obtained from (4) and (5) where d is the Euclidean distance between transmitting node and receiving node, The free space model and the multipath fading channel model are used in the construction of the radio model.

TABLE IV. GLOBAL UPDATED PHEROMONE

Fig. 3. Data transmission from source to destination

TABLE V. SIMULATION PARAMETERS

ETX (k,d) Eelec*k Eamp*k*d 2

Eelec*k Eamp*k*d 4

if d do if d do

(4)

The energy consumption for message transmitting depends highly on the distance between the transmitter and the receiver using the free space and the multi-path fading channel models. So the energy consumption can be reduced

ERX

(k)

Eelec*k

(5)

by keeping the transmission distance (from cluster-heads to the sink) low using multi-hop relaying between the cluster- heads and the base station. The results of the overall energy

Eelec and Eamp are the energy dissipated by transmitter electronics and amplifier respectively and k is the packet length of the data transmitted. This radio model consists of three radio modules: transmitter, power amplifier, and receiver. The transmitter dissipates energy to run the transmitter circuitry and power amplifier for transmitting data and the receiver dissipates energy to run the receiver circuitry for receiving data.

The overall energy consumed for data transmission from source to destination is the sum of the energy consumed for both intra-cluster communication and inter-cluster communication. For analyzing the energy consumption of sensor nodes, the following simulation parameters are considered and the values are tabulated in Table V.

analysis are tabulated in Table VI.

Thus it is shown that routing through optimized path is more efficient than direct transmission from source to destination. By combining data aggregation with energy efficient optimized routing technique, a reduction in the amount of data transmitted is achieved and thus less consumption of energy. Total amount of energy consumed for different rounds of iterations are analysed which is shown in Fig. 4. As a result of the energy analysis performed, it shows that Clustering method and ACO algorithm are some of the energy efficient techniques that are applied to the routing problem in wireless sensor networks which save the power of nodes by reducing the transmission energy for long distant communication.

k-bit message

ETX

TABLE VI. ENERGY ANALYSIS

Eelec * k

k-bit message

d

Eamp *k * d

ERX

Receive Electronics

Eelec * k

Fig. 4. Heinzelman First order radio model

Fig. 5. Total energy of the system at different rounds of iterations

The application of Ant Colony meta-heuristic approach to identify the optimal path between Cluster heads and the base station in a densely deployed network has been studied. The optimal path has been calculated based on pheromone concentration in homogeneous environment.

V. CONCLUSION

A careful study on the performance of ACO algorithm is carried out, mainly on the average energy consumption. The simulation results show that the routing algorithm implemented by ACO can reduce consumption of energy effectively. As a consequence, transmission energy is reduced using multi-hop transmission when compared to one-to-one transmission. Hence Clustering approach along with ACO routing algorithm prove to be an effective way to reduce the energy consumption and thereby prolong the lifetime of WSNs.

REFERENCES

1. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless sensor networks: a survey, Computer Networks, vol. 38, no. 4, pp. 393422, 2002.

2. A. Gogu, D. Nace, A. Dilo and N. Mertnia, Optimization problems in wireles sensor networks, in Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems (CISIS 11), pp. 302309, Seoul, Republic of Korea, July 2011.

3. G. Anastasi, M. Conti, M. Francesco, A. Passarella, Energy Conservation in Wireless Sensor Networks: A survey, Ad Hoc Networks, vol. 7, pp. 537-568, 2009.

4. P. Kumarawadu, D. J. Dechene, M. Luccini, A. Sauer, Algorithms for Node Clustering in Wireless Sensor Networks: A Survey, in Proceedings of 4th International Conference on Information and Automation for Sustainability, Colombo, Sri Lanka, pp. 295300, December 2008.

5. O. Younis and S. Fahmy, HEED: A Hybrid Energy Efficient Distributed Clustering Approach for Ad-Hoc Sensor Networks, IEEE Transactions on Mobile Computing, vol. 3, no. 4, Oct-Dec 2004.

6. T. Mohamed Mubarak, Syed Abdul Sattar, G. Appa Rao, M. Sajitha, Intrusion detection: An Energy efficient approach in Heterogeneous WSN, in Proceedings of IEEE International Conference on Emerging Trends in Electrical and Computer Technology, vol. 3, pp. 1092-1096, 2011.

7. Al-Karaki, A. Kamal, Routing Techniques in Wireless Sensor networks: A Survey, Security and Networks, vol. 11, pp. 6-28, 2004.

8. S. Yi, J. Heo, Y. Cho, J. Hong, Power-efficient and adaptive clustering hierarchy protocol for wireless sensor networks, Computer Communications, vol. 30, pp. 2842-2852, October 2007.

9. 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 the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, pp. 4959, Brussels, Belgium, 2006.

10. 10. M. Dorigo, V. Maniezzo and A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, vol. 26, no. 1, pp. 2941, 1996.

11. S. Okdem and D. Karaboga, Routing in wireless sensor networks using an ant colony optimization (ACO) router chip, Sensors, vol. 9, no. 2, pp. 909921, 2009.

12. Hong-Chi Shih, Shu Chuan Chu, John F. Roddick, Mao Hsiung Hung, Jeng Shiang Pan, Power Reduction of Wireless Sensor Networks Using Ant Colony Optimization, International Conference on Computational Aspects of Social Networks, pp. 464-467, 2010.

13. Y. Zhang, L. D. Kuhn and M. P. J. Fromherz, Improvements on ant routing for sensor networks, in Proceedings of the 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 04), Brussels, Belgium, September 2004.

14. A. Salehpour, B. Mirmobin, A. Afzali-Kusha, S. Mohammadi, An Energy Efficient Routing Protocol for Cluster-Based Wireless Sensor Networks Using Ant Colony Optimization, in Proceedings of the Innovations in Information Technology, Al Ain, United Arab Emirates, pp. 455459, December 2008.

15. S. Ehsan, B. Hamdaoui, A Survey on Energy-Efficient Routing Techniques with QoS Assurances for Wireless Multimedia Sensor Networks, IEEE Communication. Surveys Tuts., vol. 14, pp. 265-278, 2011.

16. R. Ghasem Aghaei, M. A. Rahman, W. Gueaieb Ant Colony-Based Many-to-One Sensory Data Routing in Wireless Sensor Networks, in Proceedings of the Computer Systems and Applications, 2008 IEEE/ACS International Conference, Doha, Qatar, pp. 10051010, April 2008.

17. A. Gogu, D. Nace, A. Dilo and N. Mertnia, Optimization problems in wireless sensor networks, in Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems (CISIS 11), pp. 302309, Seoul, Republic of Korea, July 2011.

18. Sharma. T, Kumar. B, Berry. K, Dhawan. A, Rathore. R. S, Gupta. V, Ant Based Cluster Head Election Algorithm in Wireless Sensor Network to Avoid Redundancy, in Proceedings of Fourth International Conference on Communication Systems and Network Technologies (CSNT), pp. 83-88, April 2014.

19. Jung-Yoon Kim, Tripti Sharma, Brijesh Kumar, G. S. Tomar, Karan Berry and Won-Hyung Lee, Intercluster Ant Colony Optimization Algorithm for Wireless Sensor Network in Dense Environment, in International Journal of Distributed Sensor Networks, 2014.