Review
Classical and swarm intelligence based routing protocols for wireless sensor networks: A survey and comparison

https://doi.org/10.1016/j.jnca.2012.03.004Get rights and content

Abstract

High efficient routing is an important issue for the design of wireless sensor network (WSN) protocols to meet the severe hardware and resource constraints. This paper presents a comprehensive survey and comparison of routing protocols in WSNs. The first part of the paper surveys state-of-the-art routing protocols in WSNs from classical routing protocols to swarm intelligence based protocols. The routing protocols are categorized based on their computational complexity, network structure, energy efficiency and path establishment. The second part of the paper presents a comparison of a representative number of classical and swarm based protocols. Comparing routing protocols in WSNs is currently a very challenging task for protocol designers. Often, much time is required to re-create and re-simulate algorithms from descriptions in published papers to perform the comparison. Compounding the difficulty is that some simulation parameters and performance metrics may not be mentioned. We see a need in the research community to have standard simulation and performance metrics for comparing different protocols. To this end, the final part of the paper re-simulates different protocols using a Matlab based simulator: routing modeling application simulation environment (RMASE), and gives simulation results for standard simulation and performance metrics which we hope will serve as a benchmark for future comparisons for the research community.

Introduction

A sensor network is an infrastructure composed of sensing (measuring), computing, and communication elements that gives a user or administrator the ability to instrument, observe, and react to events and phenomena in a specific environment (Akkaya and Younis, 2005, Sohraby et al., 2007, Akyildiz et al., 2002). Wireless sensor networks (WSNs) are collections of compact-size, relatively inexpensive computational nodes that measure local environmental conditions, or other parameters and forward such information to a central point for appropriate processing. WSN nodes can sense the environment, communicate with neighboring nodes, and in many cases perform basic computations on the data being collected. The environment can be the physical world, a biological system, or an information technology (IT) framework. Through advanced mesh networking protocols, these sensor nodes form a wide area of connectivity which extends the reach of cyberspace out into the physical world. The sensing circuitry measures ambient conditions related to the environment surrounding the sensor, which transforms them into an electric signal. Processing such a signal reveals some properties about objects located and/or events happening in the vicinity of the sensor. The sensor sends such collected data, usually via radio transmitter, to a command center (sink) either directly or through a data concentration center (a gateway). The decrease in the size and cost of sensors, resulting from such technological advances, has fueled interest in the possible use of a large set of disposable unattended sensors. Such interest has motivated intensive research in the past few years addressing the potential of collaboration among sensors in data gathering and processing and the coordination and management of the sensing activity and data flow to the sink. A natural architecture for such collaborative distributed sensors is a network with wireless links that can be formed among the sensors in an ad hoc manner.

The backbone of WSNs lies in the ability to deploy large number of tiny nodes that assemble and configure themselves for a specific purpose. WSN is used in many applications such as radiation and nuclear-threat detection systems, weapon sensors for ships, toxins and to trace the source of the contamination in public-assembly locations, structural faults (e.g., fatigue-induced cracks) in ships, volcanic eruption, earthquake detection, aircraft, and buildings, biomedical applications, habitat sensing, and seismic monitoring. More recently, interest has focused on networked biological and chemical sensors for national security applications, physical security, air traffic control, traffic surveillance, video surveillance, industrial and manufacturing automation, process control, inventory management, distributed robotics, weather sensing, environment monitoring, national border monitoring, building and structure monitoring (Sohrabi et al., 2000). The most common application of sensor network technology is to monitor remote environments for low frequency data trends. For example, a chemical plant could be easily monitored for leaks by hundreds of sensors that automatically form a wireless interconnection network and immediately report the detection of any chemical leaks. Unlike the traditional wired systems, deployment cost is set to a minimum (Chong and Kumar, 2003). In addition to reducing the installation costs, wireless sensor networks also have the ability to adapt dynamically to changing environments. These can respond to changes in network topologies. A wireless sensor network node consists of four major parts such as

  • 1.

    Sensor unit.

  • 2.

    Processing unit.

  • 3.

    Energy source unit.

  • 4.

    Transceiver.

Depending on the area and purpose of use, additional components might be required such as localization unit, energy harvesters, position changers and monitors as shown in Fig. 1.

In many WSN applications, the deployment of sensor nodes is performed in an ad-hoc manner without proper planning or studies. Once deployed, the sensor nodes must be able to autonomously organize themselves into a wireless communication network. As sensor nodes are battery powered and expected to operate and execute their duties without attendance for a long duration of time during the application, it is difficult and even impossible to change or recharge batteries for the sensor nodes (Akyildiz et al., 2002, Chong and Kumar, 2003).

Despite the different objectives of sensor networks applications, the main function of wireless sensor nodes is to sense and collect information (data) from a target area, process, and transmit the information via a radio transmitter back to a command center where the underlying application resides (sink) (Akkaya and Younis, 2005, Sohraby et al., 2007). In order to achieve this task efficiently, an efficient routing protocol is needed to set up paths of communication between the sensor nodes (sources), and the command center (sink). The path selection must be such that the lifetime of the network is maximized. Due to the characteristics of the environment in which the sensor node is to operate, coupled with severe resource constraints in on-board energy, transmission power, processing capability, and storage limitations, this prompts for careful resource management and new routing protocols so as to counteract the differences and challenges.

Social insect communities have many desirable properties from the WSN perspective as surveyed in (Çelik et al., 2010; Saleem et al., 2010). These communities are formed from simple, autonomous, and cooperative organisms that are interdependent for their survival. Despite a lack of centralized planning or any obvious organizational structure, social insect communities are able to effectively coordinate themselves to achieve global objectives. The behaviors which accomplish these tasks are emergent from much simpler behaviors or rules that the individuals are following. The coordination of behaviors is also adaptive, flexible and robust, and necessary in an unpredictable world which is capable of solving real world problems. No individual is critical to any operation, and task progress can easily be recovered from any setback. The complexity of the solutions generated by such simple individual behaviors indicates that the whole is truly greater than the sum of the parts (Hölldobler and Wilson, 1990). The characteristics described above are desirable in the context of sensor networks. Such systems may be composed of simple nodes working together to deliver messages, while resilient against changes in its environment. The environment of sensor network might include anything from its own topology to physical layer effects on the communications links, to traffic patterns across the network. A noted difference between biological and engineered networks is that the former have an evolutionary incentive to cooperate, while engineered networks may require alternative solutions to force nodes to cooperate (Buttyan and Hubaux, 2000, MacKenzie and Wicker, 2001). The ability of social insects to self organize relies on four principles: positive feedback, negative feedback, randomness, and multiple interactions. A fifth principle, stigmergy, arises as a product of the previous four (Roth and Wicker, 2003). In general, such self organization is known as swarm intelligence. Swarm intelligence (Dorigo and Caro, 1998) is a relatively novel field that was originally defined as “any attempt to design algorithms or distributed problem-solving devices inspired by the collective behavior of social insects and other animal societies”. However, it now generally refers to the study of the collective behavior of multi-component systems that coordinate using decentralized controls and self-organization. From an engineering point of view, swarm intelligence emphasizes the bottom-up design of autonomous distributed systems that can show adaptive, robust, and scalable behaviors. Research on this field of swarm intelligence is based on working principles of ant colonies as adopted in (Bonabeau et al., 1999; Dorigo and Caro, 1998), slime mold (Li et al., 2011), Particle swarm optimization (Liu et al., 2012) and honey bees (Saleem and Farooq, 2007b).

The process by which data and queries are forwarded efficiently between the source and the sink is an important aspect and basic feature of wireless sensor networks. The decrease in size and cost of sensor nodes due to technological advancement has encouraged researchers in the past years to engage in an intensive research on addressing the potential of collaboration among sensors in data gathering, processing, coordination, and management of the sensed data flow to the sink (Akkaya and Younis, 2005). A simple approach to accomplish this task is for each sensor node to exchange data directly with the sink (a single-hop-based approach), or allowing intermediate nodes to participate in forwarding data packets between the source and the destination (multi-hop) (Sohraby et al., 2007). Determining which set of intermediate node is to be selected to form a data forwarding path between the source and the destination is the principal task of the routing algorithm. The differences in the way data are forwarded from the nodes to the sink, leads to classifying the routing protocols.

However, many approaches have been taken by different researchers in the field of sensor networks to classify and group each of the routing protocols based on some metrics. But there has been no survey paper based on our knowledge that covers up-to-date routing protocols. Even the ones among them that treated relatively high number of protocols, tends to focus only on the conventional routing protocols (classical) or biologically inspired routing protocols (swarm intelligence). This paper presents a comprehensive up-to-date survey and comparison of routing protocols in WSNs. The first part of the paper surveys state-of-the-art routing protocols in WSNs from classical routing protocols to swarm intelligence based protocols. The routing protocols are categorized based on their computational complexity, network structure, energy efficiency and path establishment. The second part of the paper presents a comparison of a representative number of classical and swarm based protocols. Comparing routing protocols in WSNs is currently a very challenging task for protocol designers. Often, much time is required to re-create and re-simulate algorithms from descriptions in published papers to perform the comparison. Compounding the difficulty is that some simulation parameters and performance metrics may not be mentioned. We see a need in the research community to have standard simulation and performance metrics for comparing different protocols. To this end, the final part of the paper re-simulates different protocols using a Matlab based simulator; routing modeling application simulator environment (RMASE), and gives simulation results for standard simulation and performance metrics which we hope will serve as a benchmark for future comparisons in the research community. To the best of our knowledge, this is the first survey paper that combines both classical routing and swarm based routing protocols, and proposes a standard of comparison among routing protocols designers.

The rest of the paper is organized as follows. Section 2 reviews previous survey articles on WSN routing, Section 3 describes the design factors of WSNs and how they affect routing in WSNs. Section 4 discusses the taxonomy of routing protocols in WSNs. Section 5 deals with classical routing protocols. In Section 6, swarm intelligence routing protocols are discussed. Section 7 presents analytical comparison of classical and swarm intelligence routing protocols, while Section 8 deals with their experimental comparison. In Section 9, we present a general discussion of the reviewed routing protocols in WSN. And finally, Section 10 concludes the paper with proposed future direction.

Section snippets

Previous surveys of WSN routing

Routing is a very important function in the design of WSN. There have been some survey papers on routing. Akyildiz et al. (2002) surveyed protocols on wireless sensor networks, while dealing with few of the classical routing protocols and their methods of information forwarding. Their work was based on a short period of review (1999–2000). Karaki and Kamal (2004) surveyed different routing techniques in WSNs. The authors surveyed quite a number of routing protocols, but they were limited to

WSNs design and routing factors

A large number of research have been carried out to overcome the constraints of WSNs and also to solve the design and application issues. The characteristics of sensor networks and application requirements have direct impact on the network design issues in terms of network performance and capabilities (Akyildiz et al., 2002). Due to the large number of sensor nodes and the dynamics of their operating environment, these then pose unique challenges on the architectural design of sensor networks.

Taxonomy of routing protocols in WSNs

Determining which set of intermediate nodes are to be selected to form a data forwarding path between the source and the destination is the principal task of the routing algorithm. The computational complexity and the differences in the way data are forwarded from the nodes to the sink, leads to classifying the routing protocols as either classical or swarm intelligence based, and or data-centric, hierarchical, location based, network flow and quality of service (QoS) awareness (Akkaya and

Classical based data-centric routing protocols

Broadcast and unicast are two operations that sensor nodes use to communicate with each other. In data centric routing, the sink sends queries to certain regions and waits for data from the sensors located in that area. Data centric utilizes data aggregation in relaying of data, which when data are measured or arrive from a neighbor, the sensor needs to decide whether or not they are important enough to forward them (Dulman, 2005). The coding techniques used need to minimize the number of

Swarm intelligence based routing protocols

Swarm based routing protocol (Dorigo, 2001) is a promising research on ants' behavior of which many ants are blind and communication between them is based on adoption of chemicals like substance known as pheromones, produced by the ants and deposited on the paths while walking in search for food. By sensing pheromone trails, foragers can take the path to food discovered by other ants. This behavior whereby an ant is influenced by a chemical trail left by other ants was the inspiring source of

Comparison of data-centric classical and swarm intelligence routing protocols

Table 3, Table 4, Table 5, Table 6 show the main characteristics of the different routing protocols in both classical and swarm intelligence based. The tables, show the analytical comparison of all the surveyed routing protocols according to their network structure; Data-centric, Location, Hierarchical, Network flow and QoS aware. Each of the routing protocols were described based on the network structure, energy efficiency, data aggregation, location awareness, route selection and either being

Experimental parameters

We used the routing modeling application simulation environment (RMASE) (Zhang, 2005) which is a framework implemented as an application in the probabilistic wireless network simulator (Prowler) (Sztipanovits, 2004). The simulator is written and runs under Matlab, thus providing a fast and easy way to prototype applications and having nice visualization capabilities for the experimental and comparison purpose.

Prowler is an event-driven simulator that can be set to operate in either

General discussion on the reviewed routing protocols in WSN

From the high number of papers we have reviewed on routing in WSN, it is clearly seen so far that significant efforts have been made in addressing the techniques to design effective, and efficient routing protocols for WSNs. In this section we discuss the results presented in Table 3, Table 4, Table 5, Table 6, Table 18, Table 19. We also discuss some methods related to the way these protocols have been presented and evaluated, and we then build on these results to provide some indications and

Conclusions and future direction

From the review protocols it is clearly seen so far that, significant efforts have been made in addressing the techniques to design effective, and efficient routing protocols for WSNs.

The results from our Analytical comparison are reported in Table 3, Table 4, Table 5, Table 6, while that of the experimental comparison is shown in Table 18. There exist some drawbacks in the presentation of most of the routing protocols for comparison purpose for most of the routing in WSNs, apart from the

References (98)

  • N. Bulusu et al.

    GPS-less low cost outdoor localization for very small devices

    IEEE Personal Communication Magazine

    (2000)
  • L. Buttyan et al.

    Enforcing service availability in mobile adhoc WANs

    Mobile and Ad-Hoc Networking and Computing

    (2000)
  • Cai W, Jin X, Zhang Y, Chen K, Wang R. ACO based QoS routing algorithm for wireless sensor networks. In: Proceedings of...
  • T. Camilo et al.

    An energy efficient ant-based routing algorithm for wireless sensor networks

    Ant Colony Optimization and Swarm Intelligence

    (2006)
  • F. Çelik et al.

    A survey on swarm intelligence based routing protocols in wireless sensor networks

    International Journal of the Physical Sciences

    (2010)
  • Chang J-H, Tassiulas L. Maximum lifetime routing in wireless sensor networks. In: Proceedings of the advanced...
  • C.-Y. Chong et al.

    Sensor networks: evolution, opportunities, and challenges

    Proceedings of the IEEE

    (2003)
  • M. Chu et al.

    Scalable information driven sensor querying and routing for ad hoc heterogeneous sensor networks

    The International Journal of High Performance Computing Applications

    (2002)
  • X. Cui et al.

    BCEE: a balanced-clustering, energy-efficient hierarchical routing protocol

    Network

    (2009)
  • Dasgupta K, Kalpakis K, Namjoshi P. An efficient clustering-based heuristic for data gathering and aggregation in...
  • G. De-min et al.

    Based on ant colony multicast trees of wireless sensor network routing research

    Computer

    (2008)
  • Dhurandher SK, Misra S, Obaidat MS, Gupta N. QDV: a quality-of-security-based distance vector routing protocol for...
  • M. Dorigo et al.

    AntNet: distributed stigmergetic control for communications networks

    Journal of Artificial Intelligence Research

    (1998)
  • Dorigo M. Solve difficult optimization problems. Lecture notes in computer science. In: Proceedings of the 6th European...
  • Dulman SO. Data-centric architecture for wireless sensor networks. PhD dissertation. Romania;...
  • A.G.A. Elrahim et al.

    Energy aware wireless sensor network geographic routing protocol

    Universal Journal of Computer Science and Engineering Technology

    (2010)
  • Ghasemaghaei R, Mahfujur Rahman A, Abdur Rahman M, Gueaieb W, El Saddik A. Ant colony-based many-to-one sensory data...
  • Ghasemaghaei R, Rahman MA, Gueaieb W, El Saddik A. Ant colony-based reinforcement learning algorithm for routing in...
  • Guo W, Zhang W, Lu GA. Comprehensive routing protocol in wireless sensor network based on ant colony algorithm. In:...
  • He T, Stankovic JA, Lu C, Abdelzaher T. SPEED: a stateless protocol for real-time communication in sensor networks. In:...
  • S.M. Hedetniemi et al.

    Survey of gossiping and broadcasting in communication networks

    Networks

    (1988)
  • W.R. Heinzelman et al.

    An application-specific protocol architecture for wireless microsensor networks

    IEEE Transactions on Wireless Communications

    (2002)
  • Heinzelman WR, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor...
  • Heinzelman WR, Kulik J, Balakrishnan H. Adaptive protocols for information dissemination in wireless sensor networks....
  • B. Hölldobler et al.

    The ant

    (1990)
  • C. Intanagonwiwat et al.

    Directed diffusion for wireless sensor networking

    IEEE/ACM Transactions on Networking

    (2003)
  • Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: a scalable and robust communication paradigm for sensor...
  • W. Jietai et al.

    EAQR: an energy-efficient ACO based QoS routing algorithm in wireless sensor networks

    Chinese Journal of Electronics

    (2009)
  • D.B. Johnson et al.

    Dynamic source routing in ad hoc wireless networks

  • Kalpakis K, Dasgupta K, Namjoshi P. Maximum lifetime data gathering and aggregation in wireless sensor networks. In:...
  • J.N. Karaki et al.

    Routing techniques in wireless sensor networks: a survey

    Wireless Communications, IEEE

    (2004)
  • Karp B, HT Kung. GPSR: greedy perimeter stateless routing for wireless sensor networks. In: Proceedings of the 6th...
  • Kiri Y, Sugano M, Murata M. Self-organized data-gathering scheme for multi sink sensor networks inspired by swarm...
  • Krishnamachari B, Estrin D, Wicker S. Modeling data-centric routing in wireless sensor networks. In: Proceedings of the...
  • J. Kulik et al.

    Negotiation-based protocols for disseminating information in wireless sensor networks

    Wireless Networks

    (2002)
  • K. Li et al.

    Slime mold inspired routing protocols for wireless sensor networks

    Swarm Intelligence

    (2011)
  • Li L, Halpern JY. Minimum-energy mobile wireless networks revisited. In: Proceedings of the IEEE ICC. Helsinki Finland;...
  • C.R. Lin et al.

    Adaptive clustering for mobile wireless networks

    IEEE Journal on Selected Areas in Communications

    (1997)
  • Lindsey S, Raghavendra CS, Sivalingam K. Data gathering in sensor networks using the energy*delay metric. In:...
  • Cited by (0)

    View full text