Cluster Based on Demand Routing Protocol for Mobile Ad Hoc Network

Cluster Based on Demand Routing Protocol for Mobile Ad Hoc Network

Neha Gupta Er. Manish Shrivastava Angad Singh

Deptt. of IT Head of Deptt. of IT Assot. Professor Deptt. of IT LNCT BHOPAL INDIA

Abstract

Mobile adhoc network (MANET) is a collection of wireless nodes that dynamically create a wireless network among them without using any infrastructure. Nodes are free to move, independent of each other which mak es routing much difficult. The routing protocols in MANET should be more dynamic so that they quick ly respond to topological changes. Mobile ad hoc network is a collection of mobile nodes communicating through wireless channels without any existing network infrastructure or centralized administration. Due of the limited transmission range of wireless network , multiple "hops" are needed to exchange data across the network . In order to facilitate communication within the network , a routing protocol is used to discover routes between nodes. The primary goal of such an adhoc network routing protocol is efficient route establishment between a pair of nodes so that messages may be delivered in a timely manner. Route construction should be done with a minimum of overhead and bandwidth consumption.

This paper mainly focuses on cluster-based routing on demand protocol. In this we use clustering's structure for routing protocol. Clustering is a process that divides the network into interconnected substructures, called clusters. ODRP creates routes on demand so they suffer fro m a route acquisition delay, although it helps reduce network traffic in general.

1. Introduction

   A Mobile Ad-hoc Netwo rk (MANET) is a te mporary wireless network composed of mobile nodes, in which an infrastructure is absent. There are no dedicated routers, servers, access points and cables. If two mobile nodes are within each others transmission range, they can communicate with each other directly. Otherwise, the nodes in between have to forward the packets for them. In such a case, every mobile node has to function as a router to forward the packets for others. Trad itional routing protocols used in hardwired networks, such as distance vector protocols (e.g. RIP) and link state

   protocols (e.g., OSPF) cannot be imple mented in the MANET directly for various reasons.

   Most research effort has been put in the routing

   protocols since the advent of the MANET. They can be divided into the two basic categories: Proactive routing protocols (DSDV, W RP, OLSR, WRP, CGSR, FSR,

   GSR) and Reactive routing protocols or on demand routing protocols (DSR, SSR, A ODV, TORA).

   The OLSR is the most widely used link state protocol,

   while AODV is the most popular distance vector protocol. Existing wo rk gives general analysis of link state routing and distance vector routing in MANET [1] [2]. Pe rformance evaluation of Destination Sequenced Distance Vector (DSDV) and Ad hoc On demand Distance Vector (AODV) routing protocols[3] by considering various performance metrics like packet delivery fraction, average end to end delay of data packets, normalized routing load. The experiments have been conducted by varying the mobility speed. It was observed that AODV outperforms DSDV in less stressful situations. Complete study and evaluation of Cluster Based Routing Protocol has been done [5]. Thorough study of unicast and multicast routing protocols with broadcast algorithm have been described [6]. Most research effort has been put in the routing protocols such as AODV and DSR[4][7].

   This paper ma inly focuses on cluster-based on demand

   routing protocol. Section 2 discusses about the clustering. Section 3 discusses the basics of few most common used routing protocols. Section 4 gives review of literature for eva luation of performance of c luster based on demand routing protocol. Fina lly conclusion is given in section 5.

2. Clustering

   We use clustering's structure for routing protocol. Clustering is a process that divides the network into interconnected substructures, called clusters. Each cluster has a cluster head (CH) as coordinator within the substructure. Each CH acts as a temporary base station within its zone or cluster and communicates with other CHs. In our protocol, there are four possible states for the node: NORMAL, ISOLATED,

   CLUSTERHEAD and GATEWAY. In itia lly a ll nodes are in the state of ISOLATED. Each node maintains the NEIGHBOR table where in the informat ion about the other neighbour nodes is stored CHs have another table (CHNEIGHBOR) where in the information about the other neighbour CHs is stored. The primary step in clustering is the CH elect ion.

3. ROUTING PROTOCOLS

   This section provides the overview of different on demand routing protocols which will be evaluated in this paper:

   1. Dynamic Source Routing Protocol (DSR)

      The key feature of this protocol is that it is a pure on demand protocol, i.e . it does not employ any periodic e xchange of packets. DSR does even employ beacon packets like some other on demand protocols. Consequently, DSR applies on demand schemes for both route discovery and route maintenance. This ma kes the routing overhead traffic scales to the actual needed size auto matica lly, wh ich is considered as the ma in advantage of DSR.

   2. Adhoc on-demand distance-vector routing protocol (AODV)

   The key feature of this protocol is that ap plying a distributed routing scheme. In contrast to the source routing applied by DSR, AODV depends on storing the next hops of a path as entries in the intermediate nodes, which is considered as an advantage. However this may require additional resources form the intermediate nodes, which is the negative side of AODV.

   2.3 Cluster-based routing protocol (CBRP)

   Clustering is usually used to speed up route discovery by structuring the overall network nodes hierarchically. Clusters are setup at start time and ma intained periodically or dyna mica lly. Routing is performed at the cluster level, while path setup inside the cluster is done by the cluster maintenance mechanis m. The cluster radius is usually set to be two or three hops.

   In the previous works on cluster based networking, a cluster network usually contains two types of links: intra-c luster link to connect nodes in a cluster and inter cluster link to connect clusters. When a cluster is created, a head node is chosen for administration of the cluster. The head node will work as a base station in the cluster to control channel access, perform power measure ments, and guarantee bandwidth for rea l t ime traffic. Each me mber node in a cluster is assigned a node ID (NID), and a cluster ID (CID). As a hierarchica l routing protocol, a cluster based routing

   usually uses proactive routing to decrease the delay at the intra-cluster path, and uses reactive routing to reduce control overhead at the inter-cluster path.

   Intr a cluster routing A cluster head has the responsibility of routing fro m the current cluster to other cluster heads. Packets will be delivered to the destination via low layer intra-cluster routing and then through a high layer inter-c luster routing.

   When a Link State Routing (LSR), a typical proactive

   routing algorithm, is chosen for intra cluster routing, each me mber node will be recognized by their head node with the NID. The head node collects all link state informat ion fro m every me mbe r node, builds an intra- cluster topology message, and advertises it to all me mbe r node inside the cluster. On receiving the message, me mber nodes can create routing tablesfor intra-c luster communications.

   Packets generated inside a cluster and packets passing through the cluster will be forwarded to the gateway node in the cluster to reach other cluster.

   Inter cluster routing When a source node wants to communicate with a node in a different cluster, a route request (RREQ) wh ich contains its address will be sent for path discovery. When the RREQ is delivered to a me mbe r node of a cluster, it will be forwa rded immed iately to its cluster head and the head checks if the destination address in the cluster. If destination is in the cluster, the head adds its CID on RREP and sends it back to the source in reverse path; otherwise, the RREQ will be forwa rded to the next cluster until it finds the destination.

   Unlike tradit ional node level mu lti-hop networks, in the cluster based routing, any me mbe r node can receive packets from outside and deliver it to the gateway node. Packet fro m a source cluster head node uses inter- cluster link to reach the (cluster level) next hop, and arrives at the gateway of the current cluster via the intra-c luster path. The packet then passes through the inter-c luster path to reach its next c luster.

4. Review of Literature

   In 2010 Yudhvir Singh Yogesh Chaba, Monika J ain and Pr abha Rani, Pe rformance Evaluation of On- De mand Multicasting Routing Protocols in Mobile Adhoc Networks, In this paper performance analysis of On De mand Multicasting Routing protocols (ODMRP) has been done by comparing it with AODV and FSR routing protocol on the basis of three different performance metrics i.e . Average throughput, packet delivery ratio and end-to-end delay. The simulat ion results shows that Average throughput of ODMRP is better than AODV and FSR with the varying number of nodes and also with the increase in mobility. Packet delivery ratio for AODV is better than that of ODM RP

   and FSR with the changing number of nodes as well as with changing

   In 2007 Geetha Jayakumar and Gopinath Ganapathy, Performance Comparison of Mobile Ad- hoc Network Routing Protocol, In this paper compare the performance of two prominent on-demand routing protocols for mobile ad hoc networks: Dynamic Source Routing (DSR), Ad Hoc On demand distance Vector Routing (AODV)[9]. A detailed simulation model with MAC and physical layer models is used to study the interlayer interactions and their performance implications. They demonstrate that even though DSR and AODV share similar on-demand behavior, the differences in the protocol mechanisms can lead to significant performance differentials. In the paper they examine two on demand routing protocols AODV and DSR based on packet delivery ratio, normalized routing load, normalized MAC load, average end to end delay by varying the number of sources, speed and pause time.

   In this paper we have compared the performance of AODV and DSR routing protocols for ad hoc networks using ns-2 simulat ions. Unfortunately, TORA simu lations couldnt be successfully carried out. AODV and DSR use the reactive On-de mand routing strategy. Both AODV and DSR perform better under high mobility simu lations. High mobility results in frequent lin k failures and the overhead involved in updating all the nodes with the new routing informat ion as in DSDV is much more than that involved AODV and DSR, where the routes are created as and when required. DSR and AODV both use on-demand route discovery, but with different routing mechanics. In particular, DSR uses source routing and route caches, and does not depend on any periodic or timer -based activities. DSR e xp lo its caching aggressively and ma intains mu ltiple routes per destination. AODV, on the other hand, uses routing tables, one route per destination, and destination sequence numb ers, a mechanis m to prevent loops and to determine freshness of routes. The general observation from the simulat ion is that for application-oriented metrics such as packet delivery fract ion and delay. AODV, outperforms DSR in more stressful situations (i.e., sma ller number of nodes and lower load and/or mobility), with widening performance gaps with increasing stress (e.g., more load, higher mobility). DSR, however, consistently generates less routing load than AODV. The poor performances of DSR are ma inly attributed to aggressive use of caching, and lack of any mechanism to expire stale routes or determine the freshness of routes when multiple choices are available . Aggressive

   caching, however, seems to help DSR at lo w loads and also keeps its routing load down. If there could be any mechanis ms to expire routes and or determine the freshness of routes in the route cache could benefit DSR performance significantly. It is found that for lower loads DSR is more effective while AODV is more effective for higher loads.

   In 2008, Jie Zhang, Choong Kyo Zeong, Goo Ye on Lee, Hwa Zong Ki m, Cluster based Multi path Routing Algorithm for Multi-hop Wireless Network. In this Paper proposed Custer based Multi path Routing (CBMPR) will achieve ma ximu m throughput and low delay by selecting multiple paths with little interferences among them.

   Cluster-Based Routing: Clustering is usually used to speed up route discovery by structuring the overall network nodes hierarchically. Clusters are setup at start time and maintained periodically or dynamically. Routing is performed at the cluster level, while path setup inside the cluster is done by the cluster ma intenance mechanism. The cluster radius is usually set to be two or three hops.

   In the previous works on cluster based networking, a cluster network usually contains two types of links: intra-c luster link to connect nodes in a cluster and inter cluster link to connect clusters. When a cluster is created, a head node is chosen for administration of the cluster. The head node will work as a base station in the cluster to control channel access, perform power measure ments, and guarantee bandwidth for rea l t ime traffic. Each me mber node in a cluster is assigned a node ID (NID), and a cluster ID (CID). As a hierarchica l routing protocol, a cluster based routing usually uses proactive routing to decrease the delay at the intra-cluster path, and uses reactive routing to reduce control overhead at the inter-cluster path.

5. Conclusion

   We proposed a Cluster Based Routing Protocol is an on-demand routing protocol, where the nodes are divided into clusters . Traditional routing algorith ms cannot satisfy the require ments of an ad hoc network, because of the dynamic topology and the limited bandwidth that characterize these networks. For this reason there is a lot of research that deal with the e xtension of the existing routing algorithms or with the discovery of new and more effic ient routing protocol.

   This paper evaluated and compared many on de mand routing protocol using the CBRP achieve a lo w Routing Overhead than AODV, and among three DSR achieve lowest routing overhead. AODV has lowest average end to end delay. Packet delivery ratio of CBRP and DSR is almost same (90 %) and is better than AODV

   which gives 82.8% PDR For all the protocols performance imp roves.

6. References

1. C. Adijh, E.Baccelli, P. Jacquet, Link state routing in wireless ad-hoc networks, Proc. Military Communications Conference (MILCOM '03), IEEE Computer Society, 2003, pp. 1274-1279.

2. Y. Lu, W. Wang, Y. Zhong, and B. Bhargava, Study of

   distance vector routing protocols for mobile ad hoc networks, Proc. First IEEE International Conference on Pervasive Computing and Communications,IEEE Computer Society, 2003.

3. P. Karavetsios, A.A. Economides, Performance

   comparison of distributed routing algorithms in adhoc mobile networks, WSEAS Transactions on Communications, Vol. 3, Issue 1, pp. 317-321, 2004.

4. Geetha Jayakumar, Gopinath Ganapathy, Performanc Comparison of M obile Ad-hoc Network Routing Protocol, International Journal of Computer Science and Network Security, VOL.7 No.1, Novemb er 2007.

5. Padmini M ishra, Routing protocols for ad hoc wireless networks http://www.cis.ohio-state.edu /~ jain/cis788- 9/adhoc _routing/index.html [2/7/2000].

6. Hongbo Zhou, A survey on routing protocols in

   MANETS: Technical report: MSU-CSE 03-08 Mar 28, 2003.

7. Falko Dressler, Self-Organization in Ad Hoc Networks: Overview and Classification, Univ of Erlangen, Dept. of Computer Science, Technical report 02/06.

   Technical report 02/06.

8. M ario Gerla, Taek Jin Kwon and Guangyu Pei, On Demand Routing in Ad Hoc Wireless Networks with Passive Clustering, Proceedings of WCNC, Sep, 2000.

9. Routing Protocols for Ad Hoc M obile Wireless Networks (http://www.cis.ohio-state.edu/~misra)

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 1 Issue 3, May – 2012