Optimised Route Selection Algorithm For 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.

A mobile ad-hoc network is a self-configuring infrastructureless network of mobile devices linked by radio waves. Multipath Multicast network support is becoming an progressively more important tool for both military and commercial distributed and group based applications. Due to the dynamic topology of the adhoc network the link break occurs causing synchronization problem which requires optimized route selection during multipath transmission. This paper focuses on the issues of the link failure and topological failure occurring in an adhoc network to ensure quality of service transmission.

Link failure occurs due to the dynamic nature of an adhoc network which is dealt with a temporary path selection technique and the topological failure is dealt with a reliable path technique. By designing an optimized route selection algorithm working in non-faded environment and using the two techniques mentioned above, both the failures can be eliminated and QoS performance can be improved during transmission of video information in ad hoc networks.

On-Demand Multicast Routing Protocol (ODMRP) [2] periodically floods the network with control packets to create and maintain the forwarding state of each node. It takes advantage of the broadcast nature of the wire-less network by its forwarding group flooding, which pro-vides a certain amount of diversity.

An on-demand multipath protocol called AOMDV [4]that extends the single path AODV protocol to compute multiple paths. AOMDV guaranteed loop freedom and disjointness of alternate paths. Performance comparison of AOMDV with AODV using ns-2 simulations shows that AOMDV is able to effectively cope with mobility-induced route failures. In particular, it reduces the packet loss by up to 40% and achieves a remarkable improvement in the end-to-end delay. AOMDV also reduces routing overhead by about 30% by reducing the frequency of route discovery operations.

Multicast [3] is an essential technology for many applications, such as group video conferencing and video distribution, and results in bandwidth savings as compared to mul-

tiple unicast sessions. To the best of our knowledge, multi-cast video communication over wireless ad hoc networks has not been studied extensively.

2. Optimised Route Selection

In on demand temporary route selection, a temporary path is created to eliminate the link failure in an ad hoc network and in disjoint path set selection the topological failures is eliminated through a multiple redundant path selection. In this algorithm, both the link failures as well as topological failure are eliminated by creating a temporary path empowered with multiple redundant paths for efficient routing. The standard AODV algorithm is modified to design such an optimized route selection algorithm.

2.1 Generating Of Route Request

In a non-fading environment an ad hoc node disseminates a RREQ when it determines that it needs a route to a destination. This can happen if the destination is previously unknown to the node or if previously valid routes to the destination expire or is marked as invalid. The sequence number of the destination is copied to the Destination Sequence field in the RREQ message from the routing table. If no sequence number is known, the unknown sequence number flag MUST be set. The Originator Sequence Number in the RREQ message is the node's own sequence number, which is incremented prior to insertion in a RREQ. The RREQ ID field is incremented by one from the last RREQ ID used by the current node. Each node maintains only one RREQ ID. The Hop Count field is set to zero.

Before broadcasting the RREQ, the originating node buffers the RREQ ID and the Originator IP address (its own address) of the RREQ for PATH_DISCOVERY_TIME. In this way, when the node receives the packet again from its neighbors, it will not reprocess and reforward the packet. An originating node often expects to have bidirectional communications with a destination node. In such cases, it is not sufficient for the originating node to have a route to the destination node and the destination must also have a route back to the originating node. For this to happen as efficiently as possible, any generation of a RREP by an intermediate node for delivery to the originating node should be accompanied by some action that notifies the destination about a route back to the originating node.

2.2 Generating Route Reply

If the node generating the RREP is not the destination node, but instead is an intermediate hop along the path from the discoverer to the target, it copies its known sequence number for the target into the Destination Sequence Number field in the RREP message.

The intermediate node updates the forward route entry by placing the last hop node into the precursor list for the forward route entry i.e., the entry for the Destination IP Address. The intermediate node also updates its route table entry for the node originating the RREQ by placing the next hop towards the destination in the precursor list for the reverse route entry i.e., the entry for the Originator IP Address field of the RREQ message data. The intermediate node places its distance in hops from the destination (indicated by the hop count in the routing table) Count field in the RREP. The lifetime field of the RREP is obtained by subtracting the present time from the expiration time in its route table entry.

3. Local Connectivity maintenance

Every node keep the track of its next active hops from the forwarding node during the last Active_Timeoutroute, as well as neighbors that have transmitted Hello messages during the last Allowed_Hello_Loss * Hello_Interval. A node can maintain exact information about its continued connectivity to these dynamic next hops, as shown below.

When every time a packet is transmitted to an active next hop, the notification of link layer determines the connectivity as provided by IEEE 802.11. For example, when even after maximum number of retransmissions if there is no link layer ACK or failure, to get CTS after sending RTS, it indicates that link to next hop has been lost

Passive acknowledgment should be used during the forwarding of packet , by listening to the channel for a transmission attempt made by the next hop if there is no layer-2 notification. If transmission is not detected within NEXTWAIT_HOP milliseconds then one of the subsequent methods should be used to decide connectivity.

Connectivity is determined by receiving any packet (including a Hello message) from the next hop.

A RREQ unicast to the next hop, asking for a route to the next hop.

If there is no link to the next hop ,the forwarding node assumes that the link is lost and corrective actions is taken.

4.Computation Method of Reliability

Node-disjoint and link-disjoint paths are the two types of multiple paths between a source and a destination . Node-disjoint paths do not have any nodes in common, except the source and destination. Link-disjoint paths do not have common links, but may have nodes in common. Although, link-disjoint paths are more available than node-disjoint paths, movement of nodes at the junctions causes the failure of all the paths going through that node. Link disjoint paths show better performance in long distance data transmission so it is considered to be highly reliable than node disjoint paths. As the nodes are in constant motion, every node will update the information about the other nodes instantly.

4.1 Assumptions

Consider the mobile adhoc network as a graph G=( V,L), where V is a set of nodes in the network, L is a set of links connecting nodes and the probability of operation is also assigned to the links. A link operates with probability plrelij, where i, j are the connected node identifiers (IDs).Each node continuously monitors the reliability of its incident links in this protocol. Reliability S→D (S≠ D) denotes the probability that there exists at least one path connecting source and destination over G graph for each source and destination pair.

4.2 Reliability Calculation

In order to acquire link reliability estimates, Path Link Expiration Time (PLET) is calculated between two nodes. Assume node i and node j are within the same transmission range, r, of each other. Let ( xi,yi) be the coordinate of node i and ( xj,yj) be that of node j. Also let vi and vj be the speeds, and θi and θj (0≤ θi, θj<2π) be the moving directions of node i and j, respectively. Then, the amount of time that the two mobile hosts will stay connected is as follows.

PLET, is given by:

PLET(i,j) (1) Where x = ai-aj, z = bi-bj,

w = vi -vj ,

y = vi -vj ,

where x and z are distance parameter w and y are angle and velocity parameters .The probability of proper operation of a link between node i and node j is calculated by:

plrelij= (2)

where PLETmax is the maximum Link Expiration Time in the network.Path reliability is defined as the probability of path 'i' between source and destination which is operational and is obtained by

cpreli= (3)

where m is the number of links making this path. A path fails with probability

cpfaili=1-cpreli (4)

Assume that cp = {cp1, cp2, … , channel Path n} denotes a disjoint path set that includes n paths. The reliability of the set is calculated by:

Reliability = 1-

= 1-

= 1-(1- cprel1- cprel2- ...- cpreln+ cprel1cprel2+...+cpreln-1cpreln -cprel1.cprel2.cprel3-....+....)

As cpreli <1, we rewrite equation as follows

Reliability≈1-(1- cprel1- cprel2- -..- cpreln ) (5)

With this value of reliability the most reliable path is selected for data transmission. After selecting the most reliable path the data is sent over that path with specified transmission optimum power given by the equation

Transmitted power = (a*d4)+c (6)

Where d is the distance between two nodes, a and c are the arbitrary constants, a=Pr*k, Pr=Minimum Received power=-91dBm, Assume k =8, a = 6.48 x 10-11 and c = 30 x 10-3W for calculations.

5. Temporary Path Selection

Due to any congestion in the network and If the data cannot be sent through the reliable path set, the data is sent through the temporary path. The data transfer through the temporary path requires a special kind of propagation and the presence of TRREQ and TRREP are required.

5.1Generating and Handling Route Temporary Request (TRREQ)

TRREQ packet is generated when a source wants to send time critical information to a destination and does not have a route to it, and broadcasts the packet to its neighbors. The TRREQ uses the following fields in its packet <Hop Count, TRREQ ID, Destination IP Address, Destination Sequence Number, Originator IP Address, and Originator Sequence Number> and the hop count (which is the number of hops from the source to the node handling the TRREQ). Thus when node receives a TRREQ, it increments the hop count by 1, when there is no path to destination it rebroadcasts the packet to its neighbors. The TRREQ is generated by means of the destination IP address and the Originator IP address which are the addresses of the destination and source respectively. The TRREQ is identified by means of TRREQ ID which is a number that uniquely identifies the TRREQ. The TTREQ is dropped when the TRREQ ID in the TRREQ packet matches the TRREQ ID in the nodes route entry table. Destination sequence number is the largest sequence number than all other sequence numbers received in the past by the originator for any route towards the destination.

5.2 Generating and Handling Temporary Route Reply (TRREP)

The TRREP packet is sent to the source , when the destination receives the TRREQ packet which increments the current destination sequence number by one .For a fixed interval of time the source waits for TRREP and then transmits the TRREQ again and retries for a predefined number of times. Source determines that destination is found to be unreachable if there is no response received . The route is marked important when the source gets TRREP and from source to destination the route is marked important. All the data that is transmitted in that route is very safely taken to the destination. A buffer is used for storing the data that is on fly without reaching destination during link failure.

6. Route Table Management

The following example demonstrates the temporary path creation in an ad hoc network during multipath multicast transmission. Due to the mobility of the nodes, finding routes in a wireless mobile ad hoc network is quite a challenging task, and takes up a lot of system resources such as bandwidth and battery power. Although it would be wise to take full advantage of the already discovered paths, many algorithms simply discard the paths if their topology has changed.

To overcome this shortcoming, a routing table maintenance procedure is used which can respond to the changes in network topology promptly, and adjusts the paths so that their lifetimes could be maximized.

Fig.1 shows the initial position of nodes. Each node maintains the list of active neighbors that are the next hop to the destination associated in the route table. It is also seen that node A is set as source node and x, y and z are set as destination nodes respectively. Using this list, Node B identifies its active neighbor and finds the temporary path. One of the selected path is A-B-C-D-Z from source node A to destination node Z. Assume node C moves out of the coverage area as shown in Fig.2 and the selected path fails. Temporary path maintenance technique is adopted to find the temporary path from source A to destination Z. The route table of a node maintains entries for each destination .The routing table has the following fields <Destination IP address, Active neighbors, Number hops, Next hop, Destination Sequence Number> and Expiration time for the routing table entry. They help the node to maintain the connectivity of the network. Whenever the link breaks, the nodes in the broken path gets special propagation (TRREQ, TRREP) and as soon as the nodes receive special propagation, the finalized route is marked important. The discovered new temporary route is cached in separate table for identifying important nodeswhich carries important data. The expiration time associated with the route depends on the size of the ad hoc network and indicates the time after which the route to that associated destination in the route table is to be removed.

The path A-B-C-D-Z breaks due to link failure and using temporary path selection technique, the source node A finds the temporary path to destination node Z and the new selected path is A-B-E-D-Z which is shown in Fig.3.

Thus the node which is assumed important is taken into consideration in ad hoc network helps in transmitting important time critical data using temporary path selection.

7. Optimized Route Selection Aodv(Orsaodv) Algorithm

Send a RREQ from source to the neighboring node which is within the transmission range.

When a node receives a RREQ packet, it decrements Max_hop by 1.

Calculate reliability = 1-Π[i=1 to n] pfaili , set pf = 0,a constant.

If the node is the destination, it updates the Prob, adds the Record and updates Prob to its route cache.

Discard the RREQ, if the max_hop value is equal to 0. Through this the number of intermediate nodes can be controlled.

Discard the RREQ, if the present ID already exists in the record.

Else rebroadcast the RREQ to the neighbors, go to step-2.

Select the reliable path set using the value of prob.

Set LDρjk to 0 if the jth and the kth path in the route cache are node disjoint, else set LDρjk= 1.

Calculate the energy function for the selected path set using the formula,

Transmitted power = (a*d4)+c,


Transmit the data through the most reliable optimal power path, if failure occur (PLET exceeds)increment pf, go to step 1 and eliminate the previously failed path.

If Cpf=3, the process repeats.

Send TRREQ to the shortest neighboring nodes, if TRREQ ID matches accept the packet and rebroadcast the TRREQ to neighbors until the TRREQ is received by the destination.


If destination receives the TRREQ it retransmits a TRREP to the source.

If source receives the TRREP, send the data through the path.

If data is transmitted successfully, set Cpf=0 and start the process again, else set destination as unreachable repeat the process.

8. Experimental Setup

The optimized route selection method addresses link and topological failure considering delay and packet loss. The aim is to evaluate the performance of multipath multicast video transmission using ORSAODV and compare it with existing AODV algorithm. To do so, the below parameters are configured in the network simulator-2:

8.1 Simulation Settings

set opt(chan) Channel/Wireless Channel

set opt(prop) Propagation/Two RayGround

set opt(netif) Phy/WirelessPhy

set opt(mac) Mac

set opt(ifq) Queue/Drop Tail/PriQueue

set opt(II) LL

set opt(ant) Antenna/OmniAntenne

set opt(x) 1000 ;#X dimension of the topography

setopt(y) 1000; # Y dimension of the topography

set opt(ifqlen) 250 ; # max packet in ifq

set opt(tr) out.tr ; # trace file

set opt(nam)out.nam ; # nam trace file

set opt(adhocRouting) ORSAODV,AODV

set opt(nn) 100 ;# how many nodes are simulated

set opt(stop)100.0 ; # simulation time

set val(engmodel) EnergyModel

set val(initeng) 1.0 ; # Initial energy in Joules

set opt(cbr)cbr$flows

setp size 1500

setopt(in) modify\modify\Verbose_DieFirma_16.dat

set rate 100 Kb

8.2 Experimental Results

In this proposal, the video information is transmitted in a multipath multicast environment by creating 100 nodes and initializing source and destination nodes using Ns-2.

The multicast transmission is done by selecting one source and four destinations. Each destination will have a separate multiple pathsets to the source.

8.3 Performance Metrics

The path set reliability for a node-disjoint and link-disjoint path is calculated for a transmission range of 200 m, and it is found that the reliability of the link disjoint path is high. It can also be seen from the fig.4 that as the transmission range increases the reliability of the link disjoint path becomes high as compared to the node-disjoint path. As the distance increases the node disjoint path becomes less reliable as the nodes are in constant motion and route table maintenance of node disjoint path is complicated. Whether it is a node disjoint or a link disjoint path, the number of paths in a pathset should be always high. When the number of paths in a pathset of the two types of disjoint paths has been compared and the link disjoint path showed better number within the transmission range of 200 meters.

From Fig.4 ,it is inferred that the path set reliability is higher for link disjoint path with respect to transmission range by 1.35 %.

Number of path sets increases the quality of service increases because of more changes of selecting the next optimal feasible path. Fig.5 shows and increase of 8% in the pathsets as the transmission range increases.

Fig.5 proves that there is an increase of pathsets by 23.33% for link disjoint technique than node disjoint.

The no. of paths in a link disjoint pathset is always high as compared to the node disjoint path. Therefore a link disjoint path is always preferred for wireless transmission.

Fig.6 shows that the path set reliability of a link disjoint path is high by 8.46%. The reliability of link disjoint path becomes even higher as more nodes are added to the network. This shows that the route table maintenance of a link disjoint path set is less complicated as compared to the node disjoint path.

The type of path set to be used, serves as a factor that increases the performance of a network. From the above results obtained, it is seen that the link disjoint path has a higher reliability when compared with node disjoint path and hence the link disjoint path is selected for the data transfer for the work done below.

Quality of Service Analysis

The QoS performance metrics are analyzed using link disjoint reliable path selection and the comparison results are given below.

8.4.1 Throughput

Throughput refers to how much data can be transferred from one location to another in a given amount of time. It is used to measure the performance of hard drives and RAM, as well as Internet and network connections. This data may be delivered over a physical or logical link, or pass through a certain network node. The throughput is usually measured in bits per second (bit/s or bps), and sometimes in data packets per second or data packets per time slot.

Fig.7 shows the comparison of throughput between the existing and proposed methods. It can be seen that the throughput has improved by 18.18% for the proposed reliable path selection algorithm.

8.4.2 Delay

As the size of the network increases the information transmission in multipath to multiple destinations is calculated. Fig8 shows, the delay has been decreased for the proposed reliable path selection algorithm than the existing algorithm.

It is the comparison of delays between existing and the proposed method which shows that the delay of the whole network has been reduced by a big margin using reliable path selection. It has also been seen that the delay has reduced considerably as the number of nodes in the network increases. More nodes are added only when the coverage area increases, so the delay of normal AODV becomes very high as the coverage area increases.

As the number of nodes goes nearer to 90 the delay in normal AODV increases rapidly but in the ORSAODV it is maintained at regular rate. This implies that the data packets reach the destination with lesser delay and thus minimizing the chances of a link failure and topological failures. From the results, it is calculated that the delay has been reduced by 49.45% in ORSAODV when compared to normal AODV.

8.4.3 Retransmitted Packets

Fig.9 shows the amount of retransmission is reduced in the reliable path selection by 31.12% when compared with existing AODV protocol. Retransmitted packets imply packet loss in the network. Thus reduction in the retransmitted packet makes the system more efficient.

9. Summary And Future Scope

In this paper, link failure and the topological failure are considered and it can be concluded that this method gives the best way to eliminate these problems. With this proposal implementation the link and the topological failures are reduced significantly.The new simulated path selection technique proves that it is much better than the existing technique with a reduction of delay by 49.45% , throughput by 18.18% and re-transmission by 31.12% which is a significant improvement. Multipath transmission is required for efficient transmission of video over wireless ad hoc networks and multicasting adds to its advantage. In future path selection along with synchronization issue will be addressed.