Exploring A New Dimension In Manets Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract--With the increasing demand of mobiles day by day the number of nodes in the mobile adhoc networks (MANETs) keeps on increasing. MANETs consist of nodes which can act as a router as well as host. With the advancement in movement of nodes the configuration of network keeps on changing. This initiates new issues in the dynamically changing scenario of routes and one has to devise for effective mechanisms and deployment for determining new routes in the network. Many routing protocols have already been devised adhering to their perspective point of view. In this paper we propose conceptually a new protocol for MANETs for minimizing maintenance overhead and consequently improving the performance.

KEYWORDS: MANETs, On-demand, Table-Driven, Backtracking, Control Overhead, Peer to peer.


In MANETs nodes reside in a peer to peer fashion and are connected to each other through single hop as well as multihop paths .Basically each node acts as an autonomous body in MANETs and these nodes are involved in route search and management process. MANETs don't have a fixed infrastructure due to the continuous random motion of nodes. As a consequence the topology of the network keeps on changing which calls for new routes and these further demands for increasing maintenance overhead.

Each node in adhoc network has self organizing characteristics and quick deployment methodology. However the discovery or maintaining the routes is always a non trivial task because not only the destination node is changing its location but also the

source may move and in this scenario it again has to deploy from beginning a destination discovery process for finding out a brand new path. Also the path from destination to source in reply process is dynamic which call for similar attention. The routing protocols are based on push-pull strategies which involve greater routing and control packets. This is possible only with enhanced bandwidth which in turn

degrades the throughput of overall system. Therefore the effective bandwidth utilization is of prime concern. Various routing protocols have been devised which have been categorized in three types namely Table Driven Routing, On Demand Routing and Hybrid Routing protocols. Table Driven Routing Involves periodical maintenance of table and this incorporates additional overhead other than routing issues. On Demand Routing don't need to maintain the tables which reduce the overhead of table maintenance. Packets are communicated in request reply fashion which considerably wastes network bandwidth and also the searching process for new routes is time taking. Hybrid Routing incorporate the better features of both the On Demand as well as the Table Driven Routing. This helps in high level scalability of adhoc networks.

The main objective of this paper is to minimize the overheads involved in route discovery and thereafter route maintenance. This helps in providing better table maintainability.

After this introduction we have given related work in section 2, proposed routing protocol in section 3, performance analysis in section 4 and finally the conclusion in last section 5.


In this section we present comparisons between various routing protocols.

There are several protocols implementing Proactive routing. Destination-sequenced distance vector (DSDV) [1] and Wireless routing protocol (WRP) are loop free protocols, however there is high overhead in DSDV and memory overhead in WRP[1] .Some protocols regarding minimization of control overheads mentioned above are DREAM , FSR, MMWN , CGSR , HSR , OLSR ,etc. However again we have some disadvantages in these protocols. Distance routing effect algorithm for mobility (DREAM) [2] requires GPS facility, Fisheye state routing (FSR) [3] reduces accuracy considerably, Multimedia support in mobile wireless networks (MMWN) [2] involves complex mobility management and cluster maintenance, Cluster-head gateway switch routing (CGSR) [2] involves cluster formation and maintenance, Hierarchical state routing (HSR) [4] involves high degree of location managenement and finally Optimized link state routing (OLSR) [2] disadvantage lies in the fact of 2-hop neighbor knowledge requirement.

There are also several protocols implementing Reactive Routing (On-demand routing). Ad hoc on-demand distance vector (AODV) [9] is adaptable to highly dynamic topologies however include some scalability issues and large delays. Dynamic source routing (DSR) [5] provides multiple routes but again the disadvantages of AODV are also prevalent here. Light-weight mobile routing (LMR) [6] and Temporally Ordered Routing Algorithm (TORA) [6] provide multiple route but these routing loops are temporary. Associativity-based routing (ABR) [7] and Signal stability adaptive (SSA) provide route stability but ensure some scalability problems. Relative distance micro-discovery ad hoc routing (RDMAR) [6] ad Location-aided routing (LAR) [2] are based on localized route discovery but since no prior information between nodes are available hence flooding concept is utilized. Ant-colony-based routing algorithm (ARA) [2] has low overhead whereas Flow oriented routing protocol (FORP) [6] employs route failure minimization technique. However both employ flooding based route discovery process.

Similarly there are several protocols implementing Hybrid Routing. Zone routing protocol (ZRP) [9] has the facility of reduced retransmission but overlapping zones. Zone-based hierarchical link state (ZHLS) [2] works with the concept of Single Point Failure. Scalable location update routing protocol (SLURP) employs location discovery using home regions. Both ZHLS [6] and SLURP [6] have drawback that they require static zone map. Distributed spanning trees based routing protocol (DST) [8] has same advantages of ZRP and has a Single Point Failure due to root node concept. Finally we have Distributed Dynamic Routing (DDR) [2] which has no zone maps which removes several hurdles in routing and the only problem which may arise is that of preferred neighbors which may become bottlenecks.

All these routing protocols might be unicast or multicast in nature. If we have a look over the development scenario of these routing protocols we find that the GSR is derived from the well known traditional link state and distance vector algorithms and maintains the network connectivity proactively. Hybrid routing protocol is based on both reactive protocol where it maintains inter-zone information as well as proactive protocols where it maintains intra-zone information. Now if we use the GPS [10] we can also make flat addressing even more effective and better manageability. DREAM is one such protocol deploying this method because here the nodes exchange only location information rather than complete link state or distance vector information.DSR[9] and AODV[9] come under On Demand routing and have to face with the scalability problem. To cope up with this problem we can localize the control message propagation to a defined region.

In next section we propose an algorithm for minimizing the constraints of above dealt in algorithms.


The main objective is to remove the overheads involved in On Demand routing. Also we try to get rid of the backtracking method which arises each time any link fails in the network. Consequently the size of the routing table is also reduced because of the avoidance of scrupulous entries.

Each node in this protocol will maintain the information regarding only those nodes which are in its range rather than of all nodes.

Node S is the source node whereas node D marks the destination node. We use a data structure for storing information of each node's identity (N-node ID) for the nodes in the route from source to destination. We also maintain a neighborhood table with the fields (N_ id, N_ dist) for maintaining distance from source to destination. Neighbors are always within the range of considerate node. The distance between two nodes relies on the duration of time of sending the RREQ (Route Request) and time of receiving the RREP (Route Reply). Thereafter based on this distance we sort the nodes accordingly.

We select a minimum path up to precedent node of destination node D. Now if the remains updated, which means that destination node has shifted its location, then we treat as temporary source node and start route request procedure from here. By doing this we minimize the backtracking concept to considerable level. All these procedures are followed recursively until we finally reach the destination node. Also we maintain the information of all nodes, basically their ID in the data structure; traversed between the source and destination nodes.

Now once the data as well as the data structure holding node identities of traversed nodes, has been received by destination node we start the Route Reply procedure. We pick the common nodes between the received data structure and those within the range of destination node D. Now the minimum distance node (A) is selected and entry from the data structure for this node is removed. A is now treated as destination node and same procedure applied. This process continues recursively unless and until we get to the destination node.


Initially assign node(S) as the source node and node (D) as the destination node.

Create a data structure (preferable an array) for storing the node identity.

n(i) indicate the number of nodes residing within the range of node i.

Sort n(i) nodes depending on their distance from node i.

Request (D)

Select the minimal distance from source until is the just previous node of destination node D.

If node is updated by destination node (D)

Then flag=1 //initially flag=0

If flag =0 then deliver the request to destination node (D).

If flag =1 then consider node as temporary node and repeat the process from step 6.

Remark: In all these steps the data structure (refer step 2) is also delivered to node just ahead in minimal path.


Select only the node in the range of destination node (D).Remove entries from data structure.

From the nodes selected go to that final node which has least distance from destination node (D). Call it A.

If A = source node (S) then finish. Otherwise step 9 and 10 are repeated treating A as D.


The above discussed algorithm has been implemented in MATLAB-7.0.In MANET's the nodes are not static in nature which causes the topology to change dynamically. This may cause the destination to move rapidly. In previous algorithms one had to start to start from the very beginning but here we come up with the concept of temporary source node which removes this constraint of starting from very beginning.

Figure 1.

In figure 1 we have developed relation between the hop count, time and number of nodes. Generally when number of nodes increase it increases the time complexity. However after the implementation using MATLAB7.0 we found that in this proposed algorithm, when number of node becomes very large then in that case the time complexity will remain stabilized with further increase in number of nodes because at that particular point the hop count will remain fixed.

Figure 2.

In figure 2 we developed a relation between time, performance and scalability. Here we find that once the hop count got fixed, with further addition of nodes the time complexity is not increased and this causes the performance to go better.


We have developed a new routing protocol for minimizing the overheads involved in route maintenance and discovery. The concept of backtracking has been minimized and this enhances the performance of algorithm to considerable level. Moreover by doing so the scalability of the network increases without hindering the performance. However testing this algorithm with very large network has not been undertaken and this lies as a future work for researchers.