International Journal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 1

ISSN 2229-5518

Optimal Path Selection Routing Protocol in

MANETs

Dr. Sapna Gambhir, Parul Tomar

AbstractAn Ad hoc network is a collection of mobile nodes forming a temporary network without the help of any centralized access poin t or existing infrastructure. In such an environment, routing protocols are required to transfer packets from source to destination as some mobile nodes can act as intermediate nodes to forward a packet to its destination, due to the limited range of each mobile no de’s wireless transmissions. Dynamic source routing (DSR) is one of the routing protocols used for ad hoc networks. In this, W hen a node requires a route to a destination, it initiates a route discovery process within the network. Source node broadcasts a route request (R REQ) packet to its neighbors, which then forward the request to their neighbors, and so on, until a route is found or all possible route per mutations have been examined. The main disadvantage of DSR protocol is that source node contains at most one route to destinati on at any moment of time. So, there is no way for the choice of optimal path for different type of applications like multimedia, voice, mail, etc . In this paper, a new protocol (DSR-A) is proposed which selects route from source to destination depending on bandwidth requirement of source node and battery life of all the nods on a path from source to destination.

Index TermsAd hoc networks, Ad hoc On Demand Distance Vector (AODV), Dynamic Source Routing (DSR ), MANET, Power Aware, Performance, OPSR

1 INTRODUCTION

—————————— ——————————
obile hosts and wireless networking are prevailing areas of research. Wireless networks are catego- rized as infrastructure based and infrastructure
less networks. Infrastructure less networks are used where it may not be economically practical or physically possible to provide the necessary infrastructure or be- cause the expediency of the situation does not permit its installation viz communication in areas affected by natu- ral disasters, war areas, in meetings and conventions in which persons wish to quickly share information etc. In such situations, mobile hosts within the same vicinity can communicate with each other without the help of fixed wired infrastructure. This type of wireless network is known as an Ad hoc network.
In Ad hoc networks, Routing protocols are required to route data packets from source to destination. Routing protocols are basically categorized in to table driven and on demand routing protocols [1]. In table driven routing protocols, up-to-date routing information is maintained by each node in the network. One or more tables are re- quired by each node in order to store routing informa- tion, and these tables are modified in response to changes in network topology by propagating updates among all nodes in the network [2]. On the other hand, on demand routing protocols concentrates on creating routes only when desired by the source node. When a node requires a route to a destination, it initiates a route discovery process within the network. In this, source node broadcasts a route request (RREQ) packet to its neighbors, which then forward the request to their neighbors, and so on, until a route is found or all possi- ble route permutations have been examined.
Ad hoc On Demand Distance Vector (AODV) [3] and Dynamic Source Routing (DSR) [4] are on demand routing protocol with the difference that nodes, that are
not on a selected path do not maintain routing informa- tion or participate in routing table exchanges. In AODV, RREQ packet received by an intermediate node contains information about its immediate source from which a RREQ packet is received whereas in DSR, RREQ packet received by destination contains name of all interme- diates nodes through which it traversed from source to destination. The main disadvantage of DSR protocol is that source node contains at most one route to destina- tion at any moment of time. So, there is no way for the choice of optimal path for different type of applications like multimedia, voice, mail, etc.
Various protocols like Ad-Hoc QoS On-Demand Routing (AQOR) [5], Flexible QoS Model for MANET (FQMM) [6], In-band Signaling system (INSIGNIA) [7] have been proposed to provide QoS in terms of band- width only. In FQMM, a combinational model of the reservation schema for high priority traffic with a service differentiation of the low priority traffic has been pro- posed. FQMM is a hybrid schema which take the advan- tage of both the per flow service granularity in IntServ and the service differentiation of DiffServ. AQOR is a resource reservation based routing and signaling algo- rithm. It provides end-to-end QoS (bandwidth and de- lay). AQOR integrates (a) on demand route discovery between the source and destination, (b) signaling func- tions for resource reservation and maintenance, and (c) hop by hop routing. INSIGNIA is the first signaling al- gorithm proposed only for MANET. In this protocol, Signaling control information is stored in the INSIGNIA option which is the IP option of the IP data packet. This algorithm is also based on the resource reservation pro- tocol.
Power-aware Source Routing Protocol for Mobile Ad Hoc Networks (PSR) [8] is an energy aware routing pro- tocol which uses the concept of link cost. In PSR, destina-

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 2

ISSN 2229-5518

tion node waits for a certain interval of time. When the time expires, destination node selects the path with min- imum cost and replies. ODMRP [9] is a mesh based scheme. This protocol makes uses of forwarding group concept. In ODMRP, source node creates group mem- bership and multicast routes whenever there is require- ment of data packet transmission. Trust Based Energy Aware AODV (TEA-AODV) [10] is an on demand routing protocol which makes use of two parameters – trust value and battery capacity of a node. TEA-AODV selects path with high reliability.
From studies, it is clear that either bandwidth or energy
awareness is the consideration parameter in existing
work but none of the protocol has taken these two pa-
rameters together to find the optimal path. Also, the ex-
isting power aware routing protocols do not take care of
the loop created by the data packet while searching the
optimal path.
A new routing protocol (DSR-A) is proposed in order to remove these disadvantages. At any moment of time, source node can have multiple routes to destination.
Source node selects the optimal path based on various parameters like type of applications, bandwidth and current battery life status of all nodes on a route to desti- nation.
Organization of the paper is as follows: Basics of DSR
protocol, its disadvantages and proposed protocol DSR-
A is discussed in section II. Section III concentrates on
experimental analysis which reflects the benefits of using
DSR-A protocol. The work is concluded in section IV.

2 PROPOSED WORK

The main objective of DSR-A is to find out the best avail- able route from source to destination depending on the type of data packet like voice, multimedia data etc sent by the source. For the proposed protocol, the base proto- col is DSR where every node has a route cache in which it caches source routes that it has learned. When source is ready to send data packet to destination, it checks its route cache for a route to destination. If route is there then it uses this route to transmit the packet oth- erwise it broadcasts RREQ packet towards the destina-
tion in order to find out the route from source to destina- tion. Each intermediate node checks its route cache for route availability. If route is available at the intermediate node then it transmits route reply (RREP) packet to- wards the source. At last, Destination receives only one RREQ packet with same sequence number and ignores the other copies of RREQ packet with same sequence number. RREQ packet received by the destination con- tains all information of intermediate nodes through which it traversed.
In the proposed (DSR-A) protocol, two new fields, re- quired bandwidth for transmission and battery life of the node itself, are added to RREQ and RREP packet respec-
tively which helps to select optimal path from source to destination. Structures of RREQ and RREP packet are shown in Table 1 and Table 2. In the proposed protocol, following considerations are there:
1. Bandwidth requirement depends on the type of data like voice data and multimedia data to be sent.
2. Battery life at any movement of time reflects the future time for which respective node is acti-
vated for sending and receiving packets and in- formation.

TABLE 1

STRUCTURE OF RREQ PACKET

TABLE 2

STRUCTURE OF RREP PACKET

Source

Destination

Battery

Nodes traversed

Three variables are required for the working of DSR_A
protocol.
1. MAX_H_COUNT: Each intermediate node cal-
culates hop count with the help of node tra- versed field in the RREQ packet. If count is more than MAX_H_COUNT then it drops the RREQ packet immediately otherwise add its identity in the node traversed field of RREQ packet and broadcast it further.
2. TIMER_DES: This variable consists of amount
of time for which destination node waits for
RREQ packets of same sequence number.
3. TIMER_SRC: This variable consists of amount
of time for which source node waits for RREP
packets of same sequence number in order to se- lect optimal path from source to destination.

Steps followed by the proposed protocol (DSR_A) are explained in Algorithm 1 and Algorithm 2.

Step 1 Source node, having data packet for the destination, checks its route cache for the destination.

Step 2 If entry is not present in route cache then go to step 3 else go to step 11.

Step 3 Source broadcasts RREQ packet towards the destination

on every possible path.

Step 4 Each intermediate node compares the required and available bandwidth at the node, if required bandwidth id greater than available bandwidth then drop the RREQ packet immediately.

Step 5 Each intermediate node calculate hop count with the help of node trace. If count increases to MAX_H_COUNT then drop the RREQ packet immediately otherwise add its identity in the node trace field of RREQ packet and broadcast it further.

Step 6 For amount of time stored in TIMER_DES, Destination sends Request Reply packets against all RREQ packets of same

sequence number.

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 3

ISSN 2229-5518

Step 7 Each intermediate node which receives RREP packet attach its bandwidth and battery capacity and forward it fur- ther.

Step 8 For amount of time specified in TIMER_SRC, source, node receives multiple RREP packet with same sequence num- ber.

Step 9 Call O_Path( RREP packets at source node, Yth,) algo-

rithm in order to find out optimal path from source to destina- tion and start sending data packets to destination through that optimum path.

Step 10 If source generates new sequence no. before receiving the first RREP packet for the same source and destination pair. It must ignore all Request Reply having old sequence no. and go to step 1.

Step 11 Use route cache entries to send data packets to destina-

Else

Yavg [j]=0;

}

If (counter==1)

send data packets to the selected path; If (counter>1)

{

Ymax= Max(Yavg[1],Yavg[2],…..Yavg[m]);

select corresponding channel with the Ymax value;

}

If (counter==0)

Retransmission of RREQ packet.

}

Algorithm 1: DSR-A Routing Algorithm

Let us consider an Ad hoc network as shown in Fig. 1 where various nodes are linked with each other. Source node A wants to send packets to destination node G. Fig.
2 shows the RREQ packets that can be received by each node. In this Fig., we assume that node G received all the four packets during the time specified in TIMER_DES.


Algorithm 2: Optimal Path Routing Algorithm

E D

Fig. 3 shows the status of RREP packets at each node in G
the network. Here, we assume that all the four packets A
are received by the source node during the time stored H

Algorithm O_Path( RREP packets at source node, Yth,)

{

B C

m= count (no_request_reply_packets);

For (j=0; j<m; j++)

{

n= count (no_nodes_visited);

x=1;

initialize the counter to 0; For(i=0 ;i<n ;i++)

{

Fig. 1. Ad Hoc Network

If (Yi<=Yth);

{

}

If (x<>0)

{

x=0;

break;

}

Yavg [j] =Sum_of Yi/n; Increment the counter;

}

————————————————

Dr. Sapna Gambhir is currently working as an Associate Professor in CE Deptt. Of YMCA University of Science and Engineering, Faridabad,India. E-mail: sapnagambhir@gmail.com

Parul Tomar is currently working as an Assistant Professor in CE Deptt.

Of YMCA University of Science and Engineering, Faridabad,India. E- mail: ptomar_p@hotmail.com

Fig. 2. A RREQ Packets from Source to Destination Node d Hoc

Network

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 4

ISSN 2229-5518


Fig. 3. RREP Packets from Source to Destination Node Fig. 4. RREQ packets towards Destination with the Condition of

Bandwidth Requirement

3 EXPERIMENTAL ANALYSIS

For the Ad hoc network shown in Fig. 4, if source node A wants to send packets to destination node G with the bandwidth requirement of 40 Mbps. The available bandwidth at each node is shown in Table 3. Fig. 4 shows various steps to transfer RREQ packets towards destination with the condition of bandwidth require- ment. Last step shows only two RREQ packets received by destination node with in the time specified in TI- MER_DES.
For the calculations, two situations are considered. First situation (best case) is when all the intermediate nodes between source and destination fulfill the requested bandwidth requirements. Second situation (worst case) is when one node on a path between source and destina- tion does not fulfill the requested bandwidth require- ments even after the k number of attempts.

TABLE 4

ABBREVIATION USED

TABLE 3

AVAILABLE BANDWIDTH AT NODES IN THE NETW ORK

Nodes

Available Band- width

(in Mbps)

A

45

B

55

C

45

D

50

E

60

F

30

G

70

H

40


In this section, we discuss how to calculate the total time required in order to send packets from source to destina- tion using basic DSR routing protocol and proposed DSR_A protocol. Various abbreviations used for this purpose are shown in Table 4.

Situation I: Best Case

Total Time)DSR = TRREQ+TRREP+ m* Tp+ Tt *(m+1) (1) (Total Time)DSR-A = TRREQ+TRREP+ m* Tp+ Tt *(m+1) + Tw at destina-

tion node+ Tp at source node

(2)

IJSER © 2012

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 5

ISSN 2229-5518

Situation II: Worst Case

(Total Time)DSR = k*{TRREQ+ TRREP + ((m/2+1) + 1)*Tp} + TRREQ +

In order to calculate percentage of saving of total time when using DSR-A routing protocol, following equation is used. The result shows 64.38% of saving in total time to send packets from source

to destination.

TRREP+ m* Tp + Tt *(m+1) (3)

(Total Time)DSR-A = 2* Tt*(m+1)* +Tw+Tp (4)

% saving (Total Time) = 100

( (Total Time)DSR - A *100 )

(Total Time)DSR

For the calculation, some values of the parameters are considered whose details are shown in Table 5.After substituting these values in equations 1-4, resulted total time for basic DSR and proposed DSR_A protocols are shown in Table 6 and corresponding graph representa- tion is shown in Fig. 5.

TABLE 5

VALUES FOR CONSIDERATION

Tp

n

Tt

Tw

k

Values (in msec.)

0.25

5

1

4

4

TABLE 6

COMPARISON TABLE OF TOTAL TIME FOR DSR AND DSR-A


The result shows 64.38% of saving in total time to send packets from source to destination.

4 CONCLUSION


This paper has presented a protocol (DSR-A) for routing packets between mobile nodes in an ad hoc network. Unlike routing protocols like dynamic source routing and ad hoc on demand distance vector routing, our pro- tocol considers various parameters like bandwidth re- quirement of source node and battery life of all the in- termediate nodes on a path to destination. Bandwidth requirement depends on the type of data used for transmission like voice, multimedia data etc. Battery life reflects high probability of path usage for transmission. Based on results of numerical analysis, DSR-A protocol is better when mobile nodes on a path between source and destination do not fulfill the requested bandwidth requirements even after many attempts. In this situation, our protocol saves 64.38% of total time to send packets to destinations.

40

35

30

25

20

15 9.5

10

5

0

36.5

13.5 13

DSR DSR_A

for Ad Hoc Mobile Wireless Networks, IEEE Personal Communica- tions, Vol. 6, April 1999,pp. 46-55.

[2] C. E. Perkins and P. Bhagwat. Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers Computer Communications, Review, pp. 234-244, October 1994.

[3] C. E. Perkins and E. M. Royer, Ad Hoc On Demand Distance Vector

November 1998

[4] J. Broch, D. B. Johnson, D. A. Maltz, The Dynamic Source Routing

Best Case Worst Case

Situation

Fig. 5. Graph Representation of total time for DSR and
DSR-A

Protocol for Mobile Ad Hoc Networks, IETF Internet Draft draft-ietf- manet-dsr-01.txt, December 1998.

[5] Qi Xue , Aura Ganz. Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks , Journal of Parallel and Distributed Computing,(63), 154-165,

2003.

[6] Hannan XIAO, Winston K.G. SEAH, Anthony LO and Kee Chiang CHUA. Flexible Quality Service Model for Ad-HOC Networks, In proceedings of the IEEE Vehicular Technology Conference, Tokio, Ja- pan, May 2000.

IJSER © 2012

http://www.ijser.org

Internatio nal Jo urnal of Scientific & Engineering Research Volume 3, Issue 7, June-2012 6

ISSN 2229-5518

[7] [ACLZ99]GS. Ahn, AT. Campbell, S-B. Lee, and X Zhang. INSIG­

NIA, Internet Draft, draft-ietf-manet-insigtUa-Ol.bct,Oct1999.

[8] Morteza Maleki, Karthik Dantu, and Massoud Pedram. Power-aware Sot=e Routing Protocol for Mobile Ad Hoc Networks, JSLPED'02, August12-14,2002, Monterey, California, USA

[9] B. Venkatalakslunil and S. Manjula Power Aware On Demand Mul-

ticast Routing protocol

[10] M. Pushpalatha, Revathi Venkataraman, and T. Ramarao "Trust Based Energy Aware Reliable Reactive Protocol in Mobile Ad Hoc Networks", World Academy of Scierce, Engineering and Te:hnology

56 2009.

IJSER lb)2012

htt p://www .'lser. ora