Comprehensive Paper on Routing Algorithms in Wireless Sensor Network

Comprehensive Paper on Routing Algorithms in Wireless Sensor Network

1Manika Rastogi, 2 Kritika Kolay, 3Akash Kumar Verma

Department of Computer Science & Engineering, HMRITM, New Delhi, India.

Abstract- A Wireless Sensor Network[2] is a collection of a large number of small, low-cost and low-power nodes (called motes) forming a temporary network where every node has a capability of sensing and forwarding the data to the other nodes by using radio frequency. Nodes can be added to and deleted from the network at any time, resulting in unpredictable changes to the topology of the network. This presents new challenges in the design of routing protocols for sensor networks. Energy consumption is the most important and critical issues for WSNs. sensor nodes communicate with each other and hence routers are selected. Routing is selected on the basis of routing protocols which are application specific. Hence route must be selected to make the communication efficient. Ad hoc networks and WSNs are similar to each other as both depend on hop-to-hop routing. So, protocols developed for ad-hoc networks are also used in many sensor applications. But sensor nodes are not much capable for these protocols. These protocols with some changes can be used in sensor networks. Moreover, extracting the strengths and weaknesses of each protocol, providing a comparison among them, including some metrics like scalability, mobility, power usage, robustness etc. to make it understandable and simple to select the most suitable one as per the requirement of the network.

Keywords Wireless Sensor Network, Sensor Nodes, Mobile Ad-Hoc Networks, Routing Algorithm.

1. INTRODUCTION

   A Wireless Sensor Network (WSN) contain hundreds or thousands of these sensor nodes[1][3] which is used to figure out the environmental or physical conditions[2] such as pressure, temperature, motion or pollutants etc. at different areas. These sensors have the ability to communicate either among each other or directly to an external base-station (BS)

   [3] by multi hop communication. A greater number of sensors allows for sensing over larger geographical regions with greater accuracy. Each sensor node bases its decisions on its mission, the information it currently has, and its knowledge of its computing, communication, and energy resources. Each of these scattered sensor nodes has the capability to collect and route data either to other sensors or back to an external base station(s).A base-station may be a fixed node or a mobile node

   capable of connecting the sensor network to an existing communications infrastructure or to the Internet where a user can have access to the reported data. Mostly, RF communication is preferred because in RF communication the size of transmitted packets is small, low data rate and frequency reuse is high. The power unit consists of energy sources such as batteries & solar cells. To make nodes mobile, a mobilize device is used which makes the node adaptive to the environment.

   Sensor nodes have restricted power supply and may have the problem of charging when battery runs out. Therefore, the mechanism for efficient power utilization consumption is necessary. Wireless sensor nodes perform three operations: event sensing, event processing and communicating with neighboring nodes. Among these, energy consumption is the major resource for communication.

   WSNs firstly convert data into radio waves and then amplify it and then radio waves are received at receiving node. Routing in WSNs is very challenging [4] [12] due to the inherent characteristics that distinguish these networks from other wireless networks like mobile ad hoc networks or cellular networks. In many applications of WSNs routing is based on the routing algorithms developed for mobile ad-hoc networks. WSNs are usually very similar to mobile ad-hoc networks (MANETs) [6]. As both are distributed network connected wirelessly, use hop-to-hop routing for communication and are battery powered. MANETs are mostly used for communication purposes and to transfer data from one device to another device through internet. But both are different in many points [9]:

   Nodes used in WSNs have very limited memory power and are of very high magnitude i.e. in order of many hundreds, as compared to MANETs.

   For WSNs communication is not very big issue, but

   collecting data is more important, while in MANETs communication is the only purpose. Because of so many differences routing mechanism for WSNs should be different.

   Sensor nodes are tightly constrained in terms of energy, processing, and storage capacities. Thus, they require careful resource management.

   Sensor networks are application specific, i.e., design requirements of a sensor network change with application.

   Almost all applications of sensor networks require

   the flow of sensed data from multiple sources to a particular BS [6]. This, however, does not prevent the flow of data to be in other forms (e.g., multicast or peer to peer).

   We have to keep in mind that routing protocols must be energy efficient in order to increase the life of sensor node and the sensor network. Routing Protocols are categorized into three categories [4] viz data centric protocols, hierarchical protocols and location based protocols. Section II describes the models of WSN into two categories: (a) Static Wireless Sensor Networks. (b) Mobile Wireless Sensor Networks. Section III describes the discussion of various (networking) routing algorithms in brief. In Section IV, conclusion is given.

2. MODELS OF WIRELESS SENSOR NETWORKS

   Sensor nodes used in wireless sensor networks can be fixed or mobile. So, according to this WSNs can be classified in two types:

   • Static Wireless Sensor Networks

   • Mobile Wireless Sensor Networks

   1. Static Wireless Sensor Network:

      It have all nodes fixed at one place, i.e. there is no motion among the nodes placed in the sensor networks. This type of network model is reliable, easy to implement. To communicate between two nodes is simple as all the nodes are static.

   2. Mobile Wireless Sensor Network

   In mobile wireless sensor networks (MWSNs), nodes are mobile [3], i.e. nodes can move from place to place. Due to which communication between two nodes can be very complicated. Routes selected for communication also have to change with respect to movement of nodes. Node which has to transfer the data, called source node, and node to which the data has to be sent is called sink node. But MWSNs are more advantageous over static WSNs in terms of MWSNs can be further divided in two parts: Sensor networks with mobile source node and sensor network with static source node.

3. ROUTING ALGORITHMS

   In general, routing in WSNs can be divided into flat-based routing, hierarchical-based routing, and location-based routing [2] depending on the network structure. In flat-based routing, all nodes are typically assigned equal roles or functionality. In hierarchical-based routing, however, nodes will play different roles in the network. So that cluster heads can do some aggregation and reduction of data in order to save energy. In location-based routing, sensor nodes positions are exploited to route data in the network. A routing protocol is considered adaptive if certain system parameters can be controlled in order to adapt to the current network conditions and available

   energy levels. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS- base, or coherent-based routing techniques depending on the protocol operation [8]. Multipath routing protocols: more than one path is used is used for the performance especially at the level of fault tolerance. Query based routing: a specific query is spread among nodes that respond accordingly. Negotiation based routing protocols: uses data descriptors to suppress duplicate data to be sent to the next sensor. QoS- based routing: comprises certain features (bandwidth, energy, etc.) over quality. Coherent based routing processing: perform in-network processing. Routing protocols can be classified into three categories, namely, proactive, reactive, and hybrid protocols [2] depending on how the source finds a route to the destination. Proactive protocols: all routes are computed before they are really needed, a routing table describing all node paths is maintained at each node, therefore called table-driven routing protocol. Reactive protocols: routes are computed on demand, also called on- demanding routing protocol. Hybrid protocols use a combination of proactive and reactive protocols. When sensor nodes are static, it is preferable to have table driven routing protocols rather than using reactive protocols.

   1. Flat Routing

      In flat networks, each node typically plays the same role [2] and sensor nodes collaborate together to perform the sensing task. Due to the large number of such nodes, it is not feasible to assign a global identifier to each node, attempt to find good-quality routes from source nodes to sink nodes by some form of flooding. Since flooding is a very costly operation [4] in resource starved networks, smart routing algorithms restrict the flooding to localized regions. Some algorithms use probabilistic techniques based on certain heuristics to establish routing paths.

      This consideration has led to data centric routing, where the BS sends queries to certain regions and waits for data from the sensors located in the selected regions. Since data is being requested through queries, such protocols can be classified as query-driven protocols. Data-driven protocols assume that there is a separate query propagation phase by which some sensor nodes realize that their data should be sent to a sink. This phase is generally also responsible for setting up routes. Protocols come under flat based routing SPIN, directed diffusion, ACQUIRE.

      1. SPIN (Sensor Protocols for Information via Negotiation): SPIN is a protocol that broadcast all the information to every node in the network. Each node has similar data with the neighboring node. This protocol distributes information to all nodes when user doesnt require exchanging data between nodes. SPIN is 3-stage protocol. It uses three messages i.e. ADV, REQ & DATA. ADV is advertising new data, REQ is request for data & DATA is the message itself. When a node wants to share data it broadcast an ADV message containing data. If the neighbor node is interested for receiving the data then it sends a REQ message back to the node for data transmission & DATA is send to the node. Nodes running

         SPIN assign a high-level name to completely describe their collected data (called meta-data) and perform meta-data negotiations before any data is transmitted. This assures that there is no redundant data sent throughout the network. Then the neighboring nodes repeat this process with its neighbors & the whole sensor area network will receive copy of the data.

         The SPIN family of protocols includes many protocols. The main two protocols are called SPIN-1 and SPIN-2[9], which incorporate negotiation before transmitting data in order to ensure that only useful information will be transferred. Also, each node has its own resource manager which keeps track of resource consumption, and is polled by the nodes before data transmission.

         The SPIN family of protocols is designed based on two basic

         ideas:

         1. Sensor nodes operate more efficiently and conserve energy by sending data that describe the sensor data instead of sending all the data; for example, image and sensor nodes must monitor the changes in their energy resources.

         2. Conventional protocols like flooding or gossiping based routing protocols waste energy and bandwidth when sending extra and un-necessary copies of data by sensors covering overlapping areas.

         One of the advantages of SPIN is that topological changes are localized since each node needs to know only its single- hop neighbors. SPIN provides much energy savings than flooding and metadata negotiation almost halves the redundant data. However, SPINs data advertisement mechanism cannot guarantee the delivery of data i.e. it has obstacles of Resource Blindness, Implosion, Overlap [10].

      2. Directed Diffusion:

         Diffusion directed routing is data centric [8]. The main function of data centric is to combine the data from different sources & enroots by saving energy, eliminating redundancy, increases lifetime, minimizing number of transmissions. In the beginning, the sink specifies low data rate for the incoming events. After that sink can reinforce a particular sensor to sends events with higher data rate. If a neighboring sensor receives this message & finding that the senders interest has higher data rate than before & this data rate is higher that of existing gradient. The directed diffusion working includes: Sending interests, building gradients & data dissemination. When interests fit gradients, paths of information flow are formed from multiple paths and then the best paths are reinforced so as to prevent further flooding according to a local rule. In order to reduce communication costs, data is aggregated on the way. The goal is to find a good aggregation tree which gets the data from source nodes to the BS. All sensor nodes in a directed diffusion-based network are application-aware, which enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in the network. Caching can increase the efficiency, robustness and scalability of coordination between sensor nodes which is the essence of the data diffusion paradigm. Other usage of directed diffusion is to

         spontaneously propagate an important event to some sections of the sensor network.

         Directed diffusion differs from SPIN in two aspects: directed diffusion issues on demand data queries as the BS send queries to the sensor nodes by flooding some tasks. In SPIN, however, sensors advertise the availability of data allowing interested nodes to query that data. And all communication in directed diffusion is neighbor-to-neighbor with each node having the capability of performing data aggregation and caching. Unlike SPIN, there is no need to maintain global network topology in directed diffusion.

         However, directed diffusion may not be applied to applications (e.g., environmental monitoring) that require continuous data delivery to the BS [13]. This is because the query driven on demand data model may not help in this regard. Moreover, matching data to queries might require some extra overhead at the sensor nodes.

      3. ACQUIRE:

      ACQUIRE is a new data centric mechanism for querying sensor network. Active query forwarding in sensor network view the network as a distributed database, where the compiles queries can be divided further into sub-queries. The working of ACQUIRE is descried as follows [11]: base station sends a query which is forwarded by each node receiving the query. During this process, each node using its pre-cached information tries to respond the query partially and then forwarded it to another sensor nodes. If pre-cached information is not update then the nodes gather information from its neighbors within a look-ahead of d hops. Once the query is resolved completely it is sent back either through the reverse path or the shortest path to the sink. ACQUIRE can also be deal with the complex queries by allowing many nodes to send response back.

      In Directed diffusion querie the data as soon as it comes to sensor nodes whereas SPIN queries data on the availability of interested sensor nodes. ACQUIRE is best among the three as it deals with complex queries by allowing many nodes to respond at a time. In directed diffusion as well as in ACQUIRE, there is neighbor-neighbor communication that is capable of performing caching but it is not required in case of SPIN.

   2. Hierarchical Routing

      Hierarchical routing is also called as cluster based routing. The main idea of developing the cluster based routing protocol is to reduce the network traffic towards the sink. The main objective of hierarchical routing is minimization of energy consumption of sensor nodes [2]. In which higher energy nodes can be used to process and send the information while the low energy nodes can be used to perform sensing task. Only low energy nodes are participate for generating network path. Hierarchical routing is two layered routing mechanism [3] where the one layer is used for selecting the cluster heads and other is used for routing. Protocols comes under hierarchical based are: LEACH, PEGASIS, TEEN, and APTEEN

      1. LEACH (Low energy adaptive clustering hierarchy):

         It randomly selects few sensor nodes as cluster heads and rotate evenly distribute the energy among the sensor in network. Cluster head node compress the data which are arriving from nodes that belong to respective cluster and send an aggregated packet to base station to reduce the amount of transmitted information. LEACH uses TDMA/CDMA MAC for reduce the intra-cluster & inter-cluster collisions [7]. Where there is a need for constant monitoring by sensor network this protocol is most appropriate.

         In order to balance the energy dissipation of nodes cluster heads change randomly over time. The decision is made by choosing a random number between 0 and 1 by the node. For the current round, node becomes a cluster head if the number is less than following threshold values:-

         Where P desired percentage of cluster heads, r is the current round; G is set of nodes that have not any cluster heads in 1/p rounds [19]. LEACH performs two tasks i.e. setup phase & steady state phase. In setup phase cluster heads are selected. In steady state phase transmission of data to the base station takes place. To minimize the overhead the duration of the steady state phase is larger than the duration of the setup phase.

      2. PEGASIS(Power efficient gathering in sensing information systems):

         PEGASIS is the enhancement over LEACH protocol, is a near optimal chain-based protocol [4].A new round will start when the round of all nodes communicate with the base station ends. This also includes the factor that the power required to transmit per round is reduced.

         Main objective of PEGASIS-

         1. Using collaborative technique increase the lifetime of each node, thus network lifetime will be increased.

         2. To reduce bandwidth consumption in communication, allow only local coordination between nodes that are close together & take turns in communication with base station.

      3. TEEN & APTEEN (Threshold sensitive energy efficient sensor network & Adaptive periodic threshold sensitive energy efficient sensor network)

         TEEN is responsive to sense the physical variations [5] such as temperature, pressure etc. In this the sensor node continuously senses the medium but the actual data transmission is done less frequently. Nodes which are closer to each other form clusters and this process is continuous in the network until the sink node is reached. The nodes cant communicate with each other if the threshold is not received & user does not get any data. Cluster head nodes broadcasts two threshold in their cluster i.e. HARD THRESHOLD & SOFT THRESHOLD. Hard threshold is the absolute value beyond which node sensing this value & switch to its transmitter when node sensing this value & report to cluster head. This threshold is used for reducing the number of transmissions by allowing the nodes only to transmit when the

         sensed attribute is in range of interest. And Soft threshold is a small change in value of sensed attribute which triggers the node to switch on its transmitter & transmit.

         APTEEN is the advancement to TEEN that changes the threshold value or periodicity of TEEN protocol according to the type of application and users conditions or needs. In APTEEN protocol cluster head broadcasts the transmission in addition with the threshold values as in TEEN. If sensor node cant send data beyond the count time then TDMA scheme

         [8] is used & each node is assigned a transmission slot.

         In LEACH, there is very low energy consumption due to distributed network whereas in PEGASIS, it takes more energy as one node is made cluster-head that receives data from other sensors. In TEEN, there is more energy consumption than in PEGASIS due to large network which is overcome in APTEEN. LEACH gives the shortest path whereas PEGASIS selects the route by greedy method but TEEN and APTEEN both gives the best route selection .In large regions, LEACH is not applicable to networks due to dynamic clustering but can be applicable in case of PEGASIS as transmitting distance is reduced. In both TEEN and APTEEN, there is a long delay in transmitting message through network.

   3. Location based routing protocols

   Location based routing protocols are using location information to guide the route discovery. In this the nodes are equipped with GPS and scattered in a particular network. The position of nodes can be determined with the help of GPS. On the basis of incoming signal strengths the distance between the neighboring nodes can be estimated. When the distance between any two nodes in the network is determined with the help of signal strength, we can know about the co- ordinates with the exchange of information or data with the neighboring nodes. Protocols come under location based routing are GAF, GEAR, GOAFR, MECN and SMECN.

   1. GAF (Geographic adaptive fidelity):

      GAF is an energy aware algorithm designed for ad-hoc networks & also be applicable to sensor networks. In this algorithm firstly, the network area is divided into fixed number of zones & form a virtual grid. In each zone, nodes play different roles with collaborating to each other. When sensor node enters the sleeping mode for energy saving, it turns off radio. In the discovery state, a sensor exchanging discovery messages to learning about other sensors in a grid. In the active state sensor continuously sends its discovering messages to inform equivalent sensors about its state [3].

   2. GEAR (Geographic & energy aware routing):

      GEAR [9] is an energy efficient routing protocol proposed for routing queries to target regions in the sensor field. In GEAR, sensors are supposed to have localization hardware equipped a GPS unit to know their current positions. GEAR uses energy aware mechanism that is based on the geographical information to select sensors to route a packet

      towards destination. Each node keeps an estimated cost and learning cost of reaching to the destination through neighbors. Estimated cost is the combination of the distance to the destination and residual energy. When a node does not have any closer neighbor to the target, a hole occurs. If there are no hole present, then the estimated cost equal to the learned cost [14].

   3. GOAFR (The Greedy Other Adaptive Face Routing):

      A geometric ad-hoc routing algorithm combining greedy and face routing was proposed. The greedy algorithm of GOAFR always picks the neighbor closest to a node to be next node for routing. However, it can be easily stuck at some local minimum, i.e. no neighbor is closer to a node than the current node. Other Face Routing (OFR) is a variant of Face Routing (FR). The Face Routing (FR) algorithm is the first one that guarantees success if the source and the destination are connected. However, te worst-case cost of FR is proportional to the size of the network in terms of number of nodes. The first algorithm that can compete with the best route in the worst-case is the Adaptive Face Routing (AFR) algorithm. Moreover, by a lower bound argument, AFR is shown to be asymptotically worst-case optimal. But AFR is not average-case efficient. OFR utilizes the face structure of planar graphs such that the message is routed from node s to node t by traversing a series of face boundaries.

      The aim is to find the best node on the boundary, i.e., the closest node to the destination by using geometric planes. When finished, the algorithm returns to the best node on the boundary. It was shown that GOAFR algorithm can achieve both worst-case optimality and average-case efficiency. Based on the simulation results of GOAFR, there are several ways to further improve the average case performance.

   4. MECN & SMECN (Minimum energy communication network & Small minimum energy communication network): MECN sets up and maintains a minimum energy network by utilizing low power GPS for wireless network [5]. It is based on two phases. Firstly, it takes the positions of a two dimensional plane and constructs an enclosure (sparse) graph, which consists from all the enclosures in the graph from each transmit nodes. Secondly, finds the optimal links on the enclosure graph. It uses distributed Bellman ford shortest algorithm with power consumption as cost metric. SMECN (small minimum energy communication network) is an extension to the MECN. In MECN, at every time it is not possible to have every node can transmit to every other node [13].

   Among all the location based routing protocols, MECN and SMECN (extension of MECN) uses minimum energy for finding smallest network. GAF and GEAR both use energy aware or energy efficient algorithm whereas GOAFR uses greedy algorithm and MECN & SMECN uses Bellman Ford shortest algorithm for finding the minimum nodes.

   In terms of energy, hierarchical protocol is the best as it efficiently maintain energy consumption of network. In

   location based protocol, energy consumption is estimated on basis of location so it may be high or low. And in Flat protocol, the energy consumption is more than the other two protocols as it waits for the data from sensors. In Flat protocol, data is transmitted to every sensors whereas in Hierarchical protocol, network clustering is pursued due to which it covers large area and in Location based protocol, data is transmitted on the basis of location information. In Flat protocol, every sensor node communicates with the sink whereas in Hierarchical protocol, one of the node is chosen as cluster head that communicates with the sink and in Location based protocol, nearest neighboring node is chosen either by its coordinate or by using GPS for communication with the sink.

4. CONCLUSION

Sensor networks are inherently different from traditional wired networks as well as wireless ad-hoc networks. However, routing algorithms for sensor networks have borrowed liberally from the existing algorithms for ad-hoc networks. In this paper we have tried to explore the space of sensor network routing. Energy efficiency is the major challenge in the field of wireless sensor networks. The common idea behind all routing protocols is to increase the life time of sensors so that they can operate as long as possible. Energy of sensors is utilized by the data transmission and reception. So routing protocol should be energy efficient. We have surveyed routing protocols and summarized research results on routing in sensor network based on network structure, which have been presented in the literature. They have the common objective of trying to extend the lifetime of the sensor network, while not compromising data delivery. Although many of these routing techniques look promising, there are still many challenges that need to be solved in the sensor networks. And a solution to most common problem for WSNs is proposed, i.e. an idea for developing a new protocol for sensor networks with the help of other routing protocols, which were basically developed for ad-hoc network. Sensor network may become an integral part of our lives because of wide range of application areas.

REFERENCES

1. G. Sartaj Sahni, Xiaochun Xu, Algorithms for Wireless Sensor Networks, 7 September 2004.

2. Pradeep Kaur, Vinay Bhardwaj Wireless Sensor Networks: A Survey,"5 May 2015.

3. Stalin Babu G, Santosh Raju D,Routing Protocols in Wireless Sensor Networks A Survey,12 May 2014.

4. Jaspinder Kaur, Taranvir Kaur, Kanchan Kaushal Survey on WSN Routing Protocols International Journal of Computer Applications (0975 8887) Volume 109 No. 10, January 2015.

5. S.Kalaiarasi IJIET, A Review on Routing Protocols in Wireless Sensor Networks.

6. Mehran Abolhasan, Tadeusz Wysocki, and Eryk Dutkiewicz , "A review of routing protocols for mobile ad hoc networks", Ad Hoc Networks, June 2003, pp.1-22.

7. Vishakha Singhal and Shrutika Suri, Comparative Study of Hierarical Routing Protocols in Wireless Sensor Networks, 31 May 2014.

8. Parul Khurana, Inderdeep Aulakh Punjab University Chandigarh, India "Wireless Sensor Network Routing Protocols: A Survey" International Journal of Computer Applications Volume 75 No. 15, August 2013.

9. Shio Kumar Singh, M p Singh and DK Singh Routing Protocols in Wireless Sensor Networks-A Survey International Journal of Computer Science &Engineering Survey (IJCSES) Vol.1,No. 2, November2010.

10. Gurveen Kaur, Vikas Goyal, Pawan Luthra,A Survey on Efficient Routing Techniques for Maximization of Network Lifetime in WSN, 8 August 2014.

11. N. Sadagopan et al., The ACQUIRE mechanism for efficient querying in sensor networks, International Workshop on Sensor Network Protocol and Applications, Anchorage, AK, May 2003.

12. Renuka Sagar, Review of Routing Protocols in Wireless Sensor Networks , 12 December 2014.

13. Kemal Akkaya, Mohamed YounisA Survey on routing protocols for wireless sensor network,2 Nov 2010.

14. Parul Tyagi, Surbhi Jain JECRC Jaipur, Comparative Study of Routing

Protocols in Wireless Sensor Network, 9 September 2012.