A Survey on Table Driven Routing Protocols in MANETs

A Survey on Table Driven Routing Protocols in MANETs

Basil Baby

Department of Computer Science & Engineering Viswajyothi College of Engineering & Technology India

Amel Austine

Department of Computer Science & Engineering Viswajyothi College of Engineering & Technology India

Shibu K R

Department of Computer Science & Engineering Viswajyothi College of Engineering & Technology India

Abstract Computer Networks has played a major role in the evolution of most modern technology especially in engineering stream. Computer Networks has set a path breaking leap in data communication and the application domain of the same is prominently increasing the day by day. Introduction of wireless network in the data communication has made tremendous changes in human history and now wireless communication has become a part of everyones life. The wide acceptance of the wireless communication is due to its efficiency and effectiveness in routing [1]. The wireless routing protocols [8] plays a big role in this. The routing protocols in wireless networks can be broadly classified into Table Driven [4][6][7][9] and On Demand[4][9][10] protocols according to how the route is being discovered. Table driven routing protocols maintain the updated information about the routes in each node where as in on demand protocols will calculate the route when it is needed. In this paper the analysis of the working principle of Table Driven wireless routing protocols like Fisheye State Routing [2], Hierarchical State Routing [3] and Zone-based Hierarchical Link State Routing Protocol [5] are compared according to the various versatile networking strategies and environment

KeywordsMANETs, Routing Protocols, Fisheye State Routing Protocol, Hirachical State Based Routing Protocols, Zone Based Routing Protocols

1. INTRODUCTION

   Wireless computer networks has wide range of application in areas like military, security systems, traffic analysis etc.. With the advancement in the technology information can be transmitted faster with great speed and security. The installation and maintenance cost of wireless network has considerably reduced which is one of the main reason why the method is becoming prominent in data communication segment.

   The wirelesses networks can be broadly classified into infra structured and infra structure less (Adhoc). Infra structured wireless networks are those the mobile nodes are connected a base station (fixed) within the range. Once the mobile node has come out of the base stations range it will be re registered to another base station. While in adhoc network all nodes are mobile. Any node can be connected or disconnected to other dynamically. Each and every node plays vital role in route discovery and forwarding.

   The wide acceptance of wireless networks is due to the efficiency of the routing protocols working underneath. The wireless routing protocols can be classified into proactive (Table Driven) [6][9] and reactive (On demand) [7]. The proactive routing protocols maintain the updated tabular information about the routing information on other nodes in the network. Whenever the topology changes, the affected nodes will propagate the update information to others so that consistent and updated information about the network topology can be maintained as a whole. Upon receiving such and update the nodes will either accept or discard according to the validity of the information. But the proactive protocols will calculate/recalculate the routing information whenever it is needed. A route discovery mechanism is invoked when the source and to send data to some destination. The routing information will be updated with this discovery and it will be kept as long as the destination is reachable or the path is invalid for some reason.

   This paper mainly focuses on the working of Adhoc wireless proactive routing protocols like Fisheye State Routing, Hierarchical State Routing, and Zone-based Hierarchical Link State Routing Protocol,

2. FISHEYE STATE ROUTING

   1. Network Model and Data Structure

      Each and every node in the network has assigned a unique identifier. An undirected link between two nodes say i,j will be formed if they are in range or it can be considered that a link between i and j is considered active as the distance between them is less. For each node i, the following information is maintained. A List Ai, three tables a) topology table TTi b) Next hop table NEXTi c) Distance Table Di. The list Ai denotes the neighboring nodes of i. The topology table TTi contains two fields TTi. LS(j) and TTi. SEQ(j). TTi. LS(j) denotes the link state information[2] denoted by the node j and TTi. SEQ(j) denotes the timestamp of the link state information from node j which will ensure the validity of the information. The table NEXTi contains NEXTi (j) which defines the next hop to which the packet has to be forwarded to destination j in the shortest possible path. The table Di has the information Di (j) which shows the shortest distance from the node i to j.

   2. Packet Routing

   In FSR routing protocol fisheye technique [2] is implemented to update the routing information between nodes. For a node i, any network topology change update information to all other nodes does not conation the information regarding all other nodes. This protocol focuses on updates regarding the link states of its neighboring nodes than remote nodes. This approach considerably reduces the link state update information traffic in the network and there by save the bandwidth.

   Fig. 1 shows the working of fisheye routing protocol with respect to node 11. The Grey colored circles and black shaded nodes show the neighboring nodes of node 11 where it exchanges link state update[2] information and all other nodes shaded white and grey are considered to be remote. So there will be no exchange of update information from node 11 to these nodes.

   Fig. 1. Fisheye Sate Routing Protocol Network Model

   This protocol enables the nodes in a particular range can exchange topology change information frequently than the remote nodes. So the case of flooding which leads to bandwidth consumption is reduced. Since the local or adjacent nodes are exchanging information, the protocol is efficiently reduces the bandwidth consumption in exchanging link state updates. Once a link state update is arrived from a neighboring node, it will be accepted based on the timestamp information. So all nodes will have the updated information in routing tables. Fig. 2 shows the routing table in each node. The bold ones are frequently updated information. This method has several advantages such as the bandwidth in conserved as the link state packets are exchanges on to neighboring nodes, routing over head is reduced as the frequency of update is different for different levels and message size of the topology is low since the topology information about far way nodes are removed. But as the network size grows this method shows performance degradation in routing since the updates are propagated among neighbors, the route calculation to remote node will become slower.

   Fig.2 Routing Tables

3. HIRACHICAL STATE BASED ROUTING PROTOCOL

   G. Pei and Gerla,X. Hong proposed a routing protocol based on network hierarchy. This protocol is based on clustering [3] network into multiple levels. Clustering entire

   network is to reduce the routing overhead and to effectively utilize the bandwidth. The clustering classified in to physical and logical clustering. Nodes clustered based on physical relationship is known as physical clusterng where logical clustering is based on logical affinity between the nodes.

   1. Network Model and Data Structure

      The network is partitioned into clusters and a cluster head

      [3] is elected. The cluster heads will again organize themselves to form higher level clusters and so on. The routing information in a particular cluster will be handled by the cluster head and the same is summarized and sent to the neighboring cluster head and the information will go in higher levels.

      Below figure shows the multi level clustering. Here the network is clustered into 4 levels. The three types of nodes in a cluster is i) cluster head {1,2,3 and 4} ii)gateway node [3]

      {6,7,8 and 11} iii)internal node{9 and 10 in cluster 3}. Cluster heads are elected at each level and they will go to higher level. An hierarchical ID is defined for each nodes. For example, the HID of node 10 is <3.3.10 >

      Fig.3. Hirachical State Based Routing Protocol Network Model

   2. Packet Routing

   Here the routing is based on HID [3]. For example if node 5(1.1.5) want to send data to node 10(3.3.10), the packet is forwarded upward levels till node 1 who is the cluster head of level three. Then the data is passed to node 3 through a virtual link and the data passes downwards till it reached node 10.

   Each and every node can update the HID to the higher levels dynamically when it receives data from the top ones. This strategy reduces the routing over head as it reduces the number of link state entries in routing table considerably.

4. ZONE BASED HIRACHICAL LINK STATE BASED ROUTING PROTOCOL

   T. Hamma, T. Katoh and Iwate-ken B.B. Bista has proposed an efficient hierarchical routing protocol in MANET using Zones. The Zone-based Hierarchical Link State Routing Protocol[5] (ZHLS) is a hierarchical protocol used MANETS. The network is divided into non over lapping zones. Nodes in a zone are aware about their physical location using location management system like GPS [5]. There are two types of connectivity which a node knows in this protocol. i) a nodes connectivity inside the zone ii) zones connectivity to the network.

   1. Network Model and Data Structure

      Fig.4 shows the zone level architecture[5] of ZHLS. The entire network is classified into non overlapping zones. The normal nodes are represented using circles and zones are marked using square boxes. Nodes in a zone is aware about its connectivity to other nodes in zone and own zone connectivity to the network. Nodes are using hierarchical ID which consist of zone ID and node ID

      Fig. 4. Zone Based Hirachical Link State Routing Protocol Network

      Model

   2. Packet Routing

   Each node has two routing tables. A intra-zone routing table[5] and inter-zone routing table[5]. The first one is used to transmit packet to a node in the same zone and second one is to sent packet to a node in other zones through a gateway node if there is at least one physical path exits between zones. This protocol uses two types of link state packets. The first one is node level link state update packet and second one is zone level link state update packet.

5. CONCLUSIONS

Routing Protocols in MANET is being classified into reactive and proactive. The proactive protocol always relay on link state update packets to keep the routing tables updated and so the nodes can intelligently sent or forward packets. But sometimes flooding of link state packets will tend to consume the network bandwidth which will degrade the overall performance. To solve problems variations are implemented in updating links states in reactive protocols. Such a kind, Fish eye routing protocol follows the concept that the neighboring nodes are to updated rather than remote nodes. This considerably reduces the performance degradation by the flooding of link states. But as the network size grows beyond the limit, the latency in delivering the packet to a remote node increases due to unknown knowledge about the path to be followed. To solve this problem another approach was implemented known as Hierarchical State Routing protocol in which the network is classified various cluster levels. Each cluster has the cluster heads are responsible for forwarding packets across the clusters. A hierarchical addressing scheme is used to identify the nodes.

This protocol efficiently route

data to local and remote nodes. But clustering into multiple levels and cluster head election become an over head in an adhoc network with nodes having high mobility. Another approach is Zone-based Hierarchical Link State Routing

Protocol which assumes the zones are not over lapped. This protocol follows intra-zone routing and inter-zone routing which cares for delivering data to local and remote nodes. But this method also will have the degradation in performance as the number of zones increases beyond a limit. All the three approaches are addressing major issues in adhoc network routing. Choosing the best table driven algorithm is purely based on the network architecture and nature of mobility of the nodes

A node in a particular zone will periodically send node level LS packet to other nodes in the same packet. The Zone level LS packets are broadcasted to other gate way nodes whenever the virtual path is broken or a new one is created.

When a pack has to be sent, the source node will look into its intra-zone routing table to check the whether the destination is in the same zone. Otherwise the node will send a location request of the source node to all other zones through its gate way node. Whenever a location request is arrived at the gateway nodes, it will check its intra-zone routing table and if the destination node is found, it will reply with the zone ID. The source node uses this information to forward the packed. During packet forwarding, the intermediate nodes will use inter zone and intra zone routing table.

REFERENCES

1. Loay Abusalah, Ashfaq Khokhar, A Survey of Secure Mobile Ad Hoc Routing Protocols, IEEE Transl. Communications Survey and Tutorials Volume: 10 Issue: 4 October 2008

2. Ting-Hung Chiu and Shyh-In Hwang, Efficient Fisheye State Routing Protocol Using Virtual Grid in High-Density Ad-hoc Networks, 8th International Conference on Advanced Communication Technology, 2006. ICACT 2006

3. G. Pei and Gerla,X. Hong, A Wireless Hierarchical Routing Protocol with Group Mobility, in Wireless Communications and Networking Conference, 1999.

4. M. Gerla and, Landmark routing for large ad hoc wireless networks, Global Telecommunications Conference, 2000. GLOBECOM '00.

5. T. Hamma, T. Katoh and Iwate-ken B.B. Bista, An Efficient ZHLS Routing Protocol for Mobile Ad Hoc Networks Database and Expert Systems Applications, 2006. DEXA '06. 17th International Workshop.

6. Syed Waqar, Zeeshan Khan, Syed Sajjad Raza, and Ahsan Suhail, Implementation of Table Driven Routing Protocol for Small Sized MANET using Bluetooth in JAVA, International Conference on Emerging Technologies, 2007. ICET 2007].

7. Khaleel Ur Rahman Khan, Rafi U. Zaman and A. Venugopal Reddy, Performance Comparison of On-Demand and Table Driven Ad Hoc Routing Protocols Using NCTUns, Tenth International Conference on Computer Modeling and Simulation, 2008. UKSIM 2008

8. Mona N. Alslaim, Haifaa A. Alaqel and Soha S. Zaghloul, A Comparative Study of MANET Routing Protocols, Third International Conference on e-Technologies and Networks for Development (ICeND), 2014

9. P. Sholander, A. Yankopolus, P. Coccoli and S.S. Tabrizi, Experimental Comparison of Hybrid and Proactive MANET Routing Protocols, Military Communications Conference 2002

10. Daxesh N. Patel, Sejal B. Patel, Hemangi R. Kothadiya, Pinakin D. Jethwa and Rutvij H. Jhaveri, A Survey of Reactive Routing Protocols In MANET, International Conference on Information Communication and Embedded Systems (ICICES), 2014