EHRP: Evolutionary Hybrid Routing Algorithm for Wireless Sensor Network

EHRP: Evolutionary Hybrid Routing Algorithm for Wireless Sensor Network

V. Krishna Kumar Assistant Professor/Computer Science Sri Ramakrishna Engineering College

Coimbatore, India

R. Vijayakumar

Assistant Professor/Computer Science Sri Ramakrishna Engineering College Coimbatore, India

1. Suresh Kumar

   Professor/Computer Science

   Sri Ramakrishna Engineering College Coimbatore, India

   Abstract Design and development of power-aware, scalable and performance-efficient routing protocols for wireless sensor networks (WSNs) is an active area of research. In this paper, we show that insect-colonies-based-intelligence commonly referred to as Swarm Intelligence (SI) serves as an ideal model for developing routing protocols for WSNs because they consist of minimalist, autonomous individuals that through local interactions self organize to produce system-level behaviors that show life-long adaptivity to changes and perturbations in an external environment. The aim of this paper is to alleviate the undesirable behavior of the EA when dealing with clustered routing problem in WSN by formulating a new fitness function that incorporates two clustering aspects, viz. cohesion and separation error The results of our experiments demonstrate that EHRP is achieving the best performance with the least communication and processing costs two main sources of energy consumption in sensor networks as compared to other SI based WSN routing protocols.

   KeywordsWSN; Routing; Hybrid Routing; Fitness Function; Swarm Intelligence.

   1. INTRODUCTION

      In recent years, the rapid development of wireless communications technology, and the miniaturization and low cost of sensing devices, have accelerated the development of wireless sensor networks (WSNs). When sprayed in a target area, they form a communication network that can sense, communicate and even react to control the environmental conditions. This makes WSNs suitable for a range of applications in diverse real world civil and military applications target field imaging, intrusion detection, weather monitoring, security and tactical surveillance and disaster management [1]. A significant limitation in current sensor nodes is low battery capacity; consequently, efficient use of the sensor nodes energy reserve is essential. The sensor node utilizes its built-in battery for communication and sensing, in the occasion of the batterys exhaustion, the sensors functionality completely halts, inevitably leading to losing parts of the networks functionality, also note that changing the batteries of large numbers of sensor nodes over wide areas with potentially unsafe terrain, as in military applications, or difficult to reach areas, as in underwater monitoring applications is practically infeasible. Consequently, much research effort has focused on maximizing the lifetime of the WSNs. A routing protocol is

      required when a source node cannot send its packets directly to its destination node but has to rely on the assistance of intermediate nodes to forward these packets on its behalf. Routing in WSNs is very challenging due to several inherent characteristics that distinguish them from contemporary communication and wireless ad hoc networks. First, it is not possible to build a global addressing scheme for the deployment of sheer number of sensor nodes. Therefore, classical IP-based protocols cannot be applied to sensor networks. Second, in contrast to typical communication networks almost all applications of sensor networks require the flow of sensed data from multiple regions (sources) to a particular sink. Third, the generated data traffic has significant redundancy in it since multiple sensors may generate same data within the vicinity of a phenomenon. Such redundancy needs to be exploited by the routing protocols to improve energy and bandwidth utilization. Fourth, sensor nodes are tightly constrained in terms of transmission power, on-board energy, processing capacity and storage. Thus, they require careful resource management [2]. The rest of the paper is organized as follows. In Section 2, we briefly summarize the well-known protocols, classical and SI, for WSNs. In Section 3, we present our proposed method that rectifies the routing problem, along with analysis of its power consumption. Section 4 presents simulation results, and finally Section 5 concludes this paper with possible future directions.

   2. RELATED WORK

      The basic function of a routing algorithm is to select the path from a set of available paths that is most efficient based on specific criteria. Intuitively, to maximize the WSNs network lifetime, the path that achieves minimum power consumption while ensuring fair power consumption among individual nodes should be used. Much effort has focused on WSN multi-hop routing algorithms, and many algorithms have been proposed [37].

      A.CLASSICAL ROUTING PROTOCOLS

      Sensor Protocol for Information via Negotiation (SPIN) [8] is a data-centric protocol that negotiates high level meta-data descriptors to perform energy-efficient routing. The data are advertised by the sources and nodes interested in the data may send a request to the advertising node. Directed

      diffusion [9] is another popular routing paradigm for WSNs, which introduces the idea of aggregation to eliminate data redundancy. The sink node floods the query containing the attributes of the required data. The source nodes located in the targeted region respond with the data which are then routed (and aggregated on the way) along the reverse links. The routes can be reinforced positively or negatively leading to increase/decrease in the data delivery rate. Low Energy Adaptive Clustering Hierarchy (LEACH) [10] organizes the sensor nodes into clusters each cluster having a cluster head. The role of the cluster head is to collect data from its members and communicate it to the base station. The nodes take turns acting as cluster heads in order to extend the networks lifetime. Power-Efficient Gathering in Sensor Information Systems (PEGASIS) [11] is a variant of LEACH protocol in which the nodes form a chain along which the data are communicated to a designated node. This node ultimately transmits it to the base station. Although it avoids the overhead of cluster formation, it is based on the same assumption as LEACH: every node can directly reach the base station.

      B.SI ROUTING PROTOCOLS

      Several routing protocols inspired by the insect colonies, ant and the honey bee, have been proposed for fixed as well as mobile ad hoc networks: AntNet [12], BeeHive [13], AntHocNet [14]. In the same spirit, a number of ant-inspired algorithms for WSNs have also been proposed [15]. In the following subsections, we provide a quick overview of four SI-based protocols for sensor networks: Flooded Piggybacked Ant Routing (FP-Ant), Flooded Forward Ant Routing (FF- Ant), Sensor-driven Costaware Ant Routing (SC-Ant) [16] and Energy-Efficient Ant-Based Routing (EEABR) [17]. EEABR is based on Ant Colony Optimization (ACO) metaheuristic [18]. Each node in the network launches forward ants at regular intervals to a specific destination. The forward ants carry the addresses of the last two visited nodes only. Other information is stored in the tables at the intermediate nodes. When the forward-ant reaches the destination node, it is converted into a backward-ant which in turn updates the probability of the path followed by the forward-ant to reach the destination node. While most of previous works have just only investigated the time change of the surviving rate of nodes in the network or the time the first node dies.Therefore, we propose an algorithm designed to achieve an extension of the functional network lifetime.

   3. EVOLUTIONARY HYBRID ROUTING PROTOCOL Meta-heuristics coordinate an interaction between local

      improvement procedures and higher level strategies to create a robust search tool for escaping local optima and tackling challenging optimization problems. One of the most popular metaheuristics is Evolutionary Algorithms (EAs). EAs inspired by the power of natural evolution, have been extensively used as search and optimization tools in various problem domains. The issue critical to a successful EA performance is the choice of a good fitness function. It forms the basis for selection, and thus facilitates improvements. More accurately, it defines what improvement means. From

      the problem-solving perspective, it represents the task to be solved in the evolutionary context. Technically, it is a function that assigns a quality measure to individual solutions. Hence, to be more precise judging the soundness of the clustering solutions provided by the routing protocol algorithm, we have to redefine the distance function to serve two clustering purposes: clusters cohesion or scatter (intra-distance) and cluster separation (inter-distance). Intra-distance can be quantified by:

      where CHs represents the number of cluster heads, Ci is the ith cluster distinguished with cluster-head CHi, and any non cluster head node, n, belongs to the cluster Ci that satisfies the smallest distance between n and CHi. Also, we can quantify inter-distance as the minimum Euclidean distance between any pair of cluster heads:

      A.SCOUTING

      We divide scouting into two steps: forward scouting and backward scouting. Forward scouting is initiated when a path to a sink node is not available. Forward scouts explore the network and look for a potential sink node. Once a sink node is found, the backward scouts establish multiple paths between the <source, sink> pair.

      B.FORWARD SCOUTING

      When an event is detected at a sensor node, it is handed over to a packer. The packer looks for an appropriate forager that might carry this event to a sink node. If the packer fails to find a forager, it launches a forward scout and encapsulates the event in its payload. Apart from the agents type field, the forward scout also carries four additional information fields in the header: scout ID, source node ID, minimum remaining energy (initialized to 1) and the number of hops (initialized to zero). The forward scout is then broadcast to the neighbors of the source node. A forward scout does not know a priori the address of the sink node. A sink node that is interested in the event, carried in the payload of a scout, will convert the forward scout into a backward scout.

      C.BACKWARD SCOUTING

      Nodes in this method maintain three types of tables: a routing table, a probability-distribution table and a forwarding table. Routing tables and probability-distribution tables are maintained by source nodes only while forwarding tables are maintained by the sink and the intermediate nodes on a given path. When a sink node receives a forward scout, it extracts the event from the payload and passes it to the application. Then it creates a new forwarding-table entry which contains

      three fields: a a unique path-ID, a next-hop ID and a previous- hop ID). The next hop is set to the sink ID, the previous-hop entry in the forwarding table is set to the node ID from which the forward scout is received. When a node i receives a backward scout from node j, it looks for a matching scout cache entry. If the information is found, it creates a forwarding table entry with the next hop set to j, path ID is set to the value contained in the header of the backward scout while the previous hop is set to the previous hop ID present in the scout cache. The scout cache entry is then flushed. No future backward scout of the current generation is entertained and therefore the node will be a part of a single route only. Finally, it compares its own energy level with the energy value contained in the header of the backward scout. If the nodes remaining energy level is lower, the field in the header is updated. Otherwise, it remains unchanged. Each intermediate node processes the backward scout in a similar way until it reaches the source node.

      D.ROUTING

      Once a route is discovered, the foragers transport events to the sink node. The source node maintains a small event cache in which the events, generated during the route discovery process, are stored. A packer then selects a forager stochastically and encapsulates the event in it. Stochastic selection is based on probability-distribution table. We maintain a window of M events and distribute them across different paths using the qnd values. A source node also acts as a sink for the neighboring sources. Therefore, it might receive foragers from its 1-hop neighbors, which we call transit packets. On reception of transit packets, a source node extracts the event and passes it to the application. The application might aggregate multiple events into a single event, in which case it then passes them down to a packer for transportation to the sink node. The reward function in this method is designed to provide loop freedom in the discovered routes. Since backward scouts follow the maximum-reward paths, they keep moving in the direction of the source node, reducing the probability of selecting a node which is at a larger distance than the current one. Moreover, the forwarding table entry at a node indicates that the backward scout has already visited this node. Therefore, if a backward scout visits a node for the second time, it is dropped by the node and the corresponding entry is flushed. In this way, we ensure that the discovered paths are loop-free.

   4. PERFORMANCE ANALYSIS

      In this section, we investigate the performance of our EHRP against the well known heuristic protocol LEACH, the EAbased protocol HCR [19] in terms of the transmission distance, transmitted data volume, energy consumption in each node and energy consumption in network, is present. These comparisons are used for the purpose of benchmarking our protocol against the well known protocols cited in the literature.

      Figure I: Performance Analysis

      The normalized routing overhead and the average used energy are shown in Fig. 1. The results demonstrate that EHRP performance in the wireless sensor network is superior in terms of all metrics. The performance enhancement is primarily due to the fact that the hierarchical design reduces the scope of the network traffic. Consequently, the sensor nodes have to share only a small part of the overall traffic- load.

   5. CONCLUSION

In this paper, we have proposed a hybrid multi-hop routing algorithm, which prolongs the network lifetime of wireless sensor networks. The results of our experiments show that EHRP delivers superior performance in terms of packet- delivery ratio and latency, but with the least energy consumption compared with other SI algorithms. The important reasons for this behavior of EHRP are: (1) a simple routing-agent model (2) fixed size of route-discovery that make the algorithm scalable to large networks, (3) distributed and decentralized control, and (4) self-organization to make it resilient to external failures. Therefore, EHRP is suitable for deployment on real sensor networks. Future research directions can be inspired from the reported results. First, the competition of LEACH with EHRP for prolonging stability period until FND may give birth to another fitness variant that can be more adaptive with the extra nodes heterogeneity. Second, it is interested to examine the effect of varying weight, w, in the fitness function on the performance of the proposed protocol. Another direction may assume the impact of varying BS location at the corner rather than at the sensor of the sensor field.

REFERENCES

1. C. Raghavendra, K. Krishna, T. Znati (Eds.), Wireless Sesor Networks, Springer-Verlag, 2004.

2. K. Akkaya, M. Younis, A survey on routing protocols for wireless sensor networks, Elsevier Ad Hoc Networks 3 (2005) 325349.

3. J. Al-Karaki, A. Kamal, Routing techniques in wireless sensor networks: a survey, IEEE Wireless Communications 11 (6) (2004) 628.

4. H. Luo, Y. Liu, S. Das, Routing correlated data in wireless sensor networks: a survey, IEEE Network 21 (6) (2007) 4047.

5. I. Khan, M. Javed, A survey on routing protocols and challenge of holes in wireless sensor networks, in: International Conference on Advanced Computer Theory and Engineering, 2008, ICACTE08, 2008. pp. 161 165.

6. K. Akkaya, M. Younis, A survey on routing protocols for wireless sensor networks, Ad Hoc Networks 3 (3) (2005) 325349.

7. J. Pan, Y.T. Hou, L. Cai, Y. Shi, S.X. Shen, Topology control for wireless sensor networks, in: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, MobiCom03, ACM, New York, NY, USA, 2003, pp. 286299.

8. W. Heinzelman, J. Kulik, H. Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, in: Proceedings of ACM/IEEE aMobiCom., Seattle, Washington, USA, 1999, pp. 174 185.

9. C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, F. Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking 11 (2003) 216.

10. W. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in: Proceedings of 33rd IEEE Hawaii International Conference on System Sciences. Cambridge, MA, USA, 2000.

11. S. Lindsey, C.S. Raghavendra, PEGASIS: power-efficient gathering in sensor information systems, in: Proceedings of IEEE Aerospace Conference. Los Angeles, CA, USA, 2002, pp. 11251130

12. G.D. Caro, M. Dorigo, AntNet: Distributed stigmergetic control for communication networks, Journal of Artificial Intelligence Research 9 (1998) 317365.

13. M. Farooq, Bee-Inspired Protocol Engineering: from Nature to Networks, Natural Computing Series, Springer-Verlag, 2009. ISBN: 978-3-540-85953-6.

14. G.D. Caro, F. Ducatelle, L.M. Gambardella, AntHocNet: an adaptive nature-inspired algorithm for routing in mobile ad-hoc networks, European Transactions on Telecommunications (ETT), Special Issue on Self Organization in Mobile Networking 16 (5) (2005) 443455.

15. M. Saleem, G.D. Caro, M. Farooq, Swarm intelligence based routing protocols for wireless sensor networks: survey and future directions, Information Sciences 181 (2010) 45974624.

16. Y. Zhang, L. Kuhn, M. Fromherz, Improvements on ant routing for sensor networks, in: Proceedings of Int. Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS), LNCS 3172. Brussels, Belgium, September 2004, pp. 154165.

17. T. Camilo, C. Carreto, J.S. Silva, F. Boavida.,An energy-efficient ant- based routing for wireless sensor networks, in: Proceedings of International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS), LNCS 4150, Brussels, Belgium, September 2006, pp. 4959.

18. M. Dorigo, T. Stützle. (Eds.), Ant Colony Optimization. MIT Press, 2004.

19. R.V. Kulkarni, A. Förster, G.K. Venayagamoorthy, Computational intelligence in wireless sensor networks: a survey, IEEE Communications Survey and Tutorials 13 (1) (2011).