Propagation Of Route Request Computer Science Essay


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

The thesis proposed two schemes EAODV-BR (Enhanced AODV with Backup Routing) and AODV_RE (AODV with Residual Energy) for route maintenance and reduction of energy consumption respectively. So the problem statement for both the proposed schemes could be given separately as:


Ad hoc networking has emerged as one of the most focused research areas in the field of wireless networks and mobile computing. Ad hoc networks consist of hosts communicating one another with portable radios. These networks can be deployed impromptu without any wired base station or infrastructure support. In ad hoc mobile networks, routes are mainly multihop because of the limited radio propagation range and topology changes frequently and unpredictably since each network host moves randomly. Therefore, routing is an integral part of ad hoc communications, and has received interests from many researchers. The proposed protocol is to remove one of the limitation of the AODV-BR i.e. consideration of mobility of nodes in the network. In AODV-BR algorithm there is a consideration of mobility of nodes for alternate path concept was used but it did not considered for the case where there is failure of both primary and alternate link. The proposed algorithm deals with this condition. It basically uses AODV-BR algorithm in its core with additional feature dealing with case of failure of both primary and alternate path.


In this work we study energy efficient routing strategy for wireless ad-hoc networks. In this kind of networks, energy is a scarce resource and its conservation and efficient use is a major issue. In MANETs, the nodes are mobile and battery operated. Since the energy is limited.  The fatal weakness of wireless network is the problem of energy consumption. Therefore energy conservation is essential for nodes rely on battery-powered. If energy of any node is lower than it threshold value, the entire network will be affected. If many routings run through the same node or two nodes use the same routing path, the energy of nodes will be depleted rapidly. Early "death" of some mobile nodes due to energy depletion may cause several problems such as network partition and communication interruption. Therefore it is required to limit the energy consumption of mobile nodes, prolong the battery life and to maintain the robustness of the system. The AODV routing mechanism does not consider the available energy of the nodes left after the simulation completed, known as residual energy. It considers only routing hop count as distance metric, as a result, unbalanced node energy consumptions occurs at each node. However, it may not be the optimal routing. Considering from the perspective of residual energy of nodes, we found this protocol is more likely to result in the death of nodes. So we propose an efficient routing algorithm, which considers both hop-count and residual energy at the route. The proposed protocol performs a route discovery process similar to the AODV protocol. The difference is to determine an optimum route by considering residual energy of nodes and hop count at the route. We carried out some simple modifications on the AODV routing protocol to ensure that the energy consumption of each node is as fair as possible in order to improve the energy consumption of the nodes and hence life of the entire network.




AODV is a very simple, well-organized and valuable routing protocol for Mobile Ad-hoc Networks which does not contain any fixed topology. It is an on-demand and distance-vector routing protocol, it means that a route is established by AODV from source to destination only on demand.

AODV is competent of both unicast and multicast routing. It uses unicast routing table along with multicast routing table. The route table is used to store the destination IP addresses, next-hop IP addresses and the destination sequence number. Routing table entry also contains lifetime field, which is updated whenever route is used. The route expires and is declared as invalid, if it is not used within its lifetime value. The methods of Route Discovery and Route Maintenance are involved for effective routing in AODV and could be given as:

4.1.1 Route Discovery

Route Discovery is used when the source node wants to send a message to a destination node. First, the source node searches its route cache to determine already existing route to the destination. If the source node finds a valid route to the destination than the route is used to send the messages. If the node does not contain a valid route to the destination, it initiates routes discovery method by broadcasting a route request (RREQ) message to all its neighbors. The route request message (RREQ) contains the source and the destination address, and a unique identification number.

Fig. 4.1 Propagation of Route Request (RREQ) Message

An intermediate node, that receives a route request message (RREQ), searches its route cache for a route to the destination. If an intermediate node founds no route to the destination, it adds its address to the route field of the message and then forwards the message to all its neighbors.

The message moves through the entire network until it reaches the destination or an intermediate node that contains a route to the destination. Then a route reply message (RREP) is generated and send back to the source node. This route reply message contains the proper hop sequences for reaching to the destination.

Reverse path setup: In addition to the RREQ-ID, two sequence numbers i.e. destination sequence number and source sequence number are included in a RREQ message as shown in Fig. 4.2. The source sequence numbers are used to maintain freshness of information about the reverse routes to the source and the destination sequence number specifies how much fresh a route to the destination must be before it could be accepted by the source.








Hop Count


Destination IP Address

Destination Sequence Number

Source IP Address

Source Sequence Number

Fig. 4.2 Route Request (RREQ) Message Format

When the RREQ message moves from the source to the destinations, it automatically set up the reverse paths from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of the RREQ message. These reverse path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.

Forward path setup: Eventually, a RREQ will arrive at a node (possibly the destination itself) that possesses a current route to the destination. If an intermediate node has a route entry for the desired destination, it determines whether the route is current by comparing the destination sequence number in its own route entry with the destination sequence number in the RREQ. If the RREQ's sequence number for the destination is greater than that recorded by the intermediate node, the intermediate node must not use its recorded route to respond to the RREQ. Instead, the intermediate node rebroadcasts the RREQ. The intermediate node can reply only when it has a route with a sequence number that is greater than or equal to that contained in the RREQ. If it has a current route to the destination and if the RREQ has not been processed previously, the node then unicast a route reply packet (RREP) back to its neighbor from which it received the RREQ as shown in fig. 4.3.

Fig. 4.3 Propagation of Route Reply (RREP) Message

A RREP message format is given as:





Prefix Size

Hop Count

Destination IP Address

Destination Sequence Number

Source IP Address

Life Time

Fig. 4.4 Route Reply (RREP) Message Format

4.1.2 Route Maintenance

Route Maintenance is used to hold route breaks. When a node faces a critical transmission problem at its data link layer then it removes the route from its route cache and sends a route error (RERR) message.

Fig. 4.5 Route Error

The route error (RERR) message is sent to all the nodes that have sent a message routed over the broken link. When a route error (RERR) message is received by the node, it removes the hop that is in error from its route cache. Acknowledgment message is used to verify the correct operation of the route links.

Fig. 4.6 Route Maintenance


AODV-BR [35] uses a mesh structure to present multiple alternate links to existing On-Demand Routing Protocols without producing other control messages. Availability of multiple alternate links in ad hoc networks are valuable because wireless networks are prone to route breaks due to node mobility, high error rate, fading environment, packet collisions and signal interference. It is important to create multiple routes without propagating further control messages than building only single route. With the limited bandwidth and shared wireless medium, it is critical in ad hoc networks to minimize the number of packets transmissions. In AODV-BR, multiple alternate links are used only when the primary route is failed or disconnected. AODV-BR protocol considers mobility of nodes for alternate links but it did not consider the case when both primary and alternate links are failed.


4.3.1 Introduction

This section presents the operation details of the first proposed method. Since the goal of our work is to improves the performance of existing On-Demand Protocol AODV-BR. So, the protocol descriptions are based on AODV-BR. The modifications to AODV-BR for applying the method are also discussed.

In the proposed protocol we try to remove one of the limitations of the AODV-BR (AODV- Backup Routing) which is consideration of mobility of the nodes in the networks. The AODV-BR protocol considers mobility of the nodes for alternate path but it does not consider the case where there is failure of both primary and alternate links. The proposed protocol deals with this condition. The proposed protocol use AODV-BR protocol in its core with some additional features that are dealing with the failure case of both primary and alternate links.

4.3.2 Operation Details of Enhanced AODV-BR Route Construction

The method can be integrated with Reactive Routing Protocols that make routes on demand via the route request and reply procedures. The proposed protocol does not require any modifications to the AODV-BR's route request (RREQ) propagation method. When the source node wants to initiate a data session to a destination but does not contain any route information, it simply searches a route by broadcasting the Route Request (RREQ) message to all its neighbors. Each RREQ message contains a unique identifier so that the node can detect and drop duplicate messages. An intermediate node when receives a non-duplicate RREQ message, it records the source node and the previous hop information in its route table (i.e., backward learning). It then rebroadcasts the RREQ message to all its neighbors. If it has a route to the destination, it sends back a Route Reply (RREP) message to the source. The destination node sends the RREP message to the source node via the selected routes when it receives the first RREQ message or subsequent RREQ messages that traversed a better route (in AODV shorter route is selected) than the previously replied routes.

During the routes reply phase a mesh structure and alternate paths are established. Similar to AODV-BR protocol methods are used in these procedures. Taking the advantages of the broadcast nature of the wireless communications, the node promiscuously "overhears" messages that are transmitted by their neighboring nodes. From these "overhears" messages, the nodes obtain alternate links information and becomes part of the mesh as follows. The node which is not part of the route, when "overhears" a RREP message not directed to itself transmit by a neighbor (on the primary route), it records that neighbor as the next hop to the destination in its alternate route table. A node may receive many RREP messages for the same route, if the nodes are within the radio propagation range of several intermediate nodes of the primary route. In this condition, the node selects the best route among them and inserts it to the alternate route table. When the source node of the route receives the RREP message, the primary route is established between the source and the destination and prepared for use. The nodes that have entries to the destination in their alternate route table are part of the mesh. The mesh structure is established together with primary and alternate links. (see Fig.4.7)

Fig. 4.7 Multiple routes Route Maintenance and Mesh Routes

There are following cases for route Maintenances

Case 1: When the primary links does not fail

In this case, primary links are used. In this case, the mobile nodes which constitute the path does not moves so that the link between then is not failed. This is the very normal case and it does not require any special handling.

Case 2: When the primary link fails but there is existence of alternate link

Data packets are delivered through the primary route unless there is a route disconnection. When a node detects a link break node 1 does not receive passive acknowledgments from node 2 a hello messages for a certain period of time, it performs a one hop data broadcast to its immediate neighbor. The node specifies in the data header that the link is disconnected and thus the packet is candidate for "alternate routing." Upon receiving this packet, neighbor nodes that have an entry for the destination in their alternate route table, unicast the packet to their next hop node. Data packets therefore can be delivered through one or more alternate routes and are not dropped when route breaks occur. To prevent packets from tracing a loop, these mesh nodes forward the data packet only if the packet is not received from their next hop to the destination and is not a duplicate. When a node of the primary route receives the data packet from alternate routes, it operates normally and forwards the packet to its next hop when the packet is not a duplicate. The node that detected the link break also sends a Route Error (RERR) message to the source to initiate a route rediscovery. The reason for reconstructing a new route instead of continuously using the alternate paths is to build a fresh and optimal route that reflects the current network situation and topology. Our alternate route utilization mechanism is similar to AODV-BR scheme which uses the mess link only to go around the broken part of route.

Case 3: When both primary and alternate links are failed

In this case, the node which discovered failure of both primary and alternate links broadcast a route request packet in the similar fashion as was done during the route construction phase and sends the route error (RERR) message to source. The node which discovers failure of both primary and alternate link will send route error (RERR) message having a sequence number, to the source and it also broadcast a route request (RREQ) message with the same sequence number as that of route error (RERR) message with source as this node (fig. 4.8. (b)) and destination being the same as original one, and in message header a additional field alternate-source having its value as this node is added. The node which receives both RERR and RREQ message with same sequence number will simply drop the RREQ message and processes RERR only, but the node which receives only RREQ message will broadcast it again, as was done in route construction phase.

Fig. 4.8 Multiple route construction and their usage: (a) showing existing primary and alternate links (b) flow of RERR and RREQ messages (c) construction of new primary and alternate links

After the reconstruction of primary and alternate link the message with the modified message header is forwarded on the newly constructed primary link (fig. 4.8. (c)).

4.3.3 Analysis and Simulation Results

We evaluate the performance of EAODV-BR through simulations. Several measurement metrics were collected from our proposed simulator to evaluate the performance of EAODV-BR.

Fig. 4.9 Comparison of packet delivery ratio with no. of sources

Fig. 4.10 Comparison of data transmission with mobility change

Fig. 4.11 Comparison of drop ratio

Fig. 4.12 Packet dropout vs. spectral range

The data packet delivery fraction is defined as the number of successfully delivered data packets to the number of data packets generated by the source. The former reflects the cost in transmitting control packet, and the other represent the efficiency of packet delivery. The data delivery fraction affected by multicast size. Size defines the number of member nodes in each multicast group. Node number defines the number of total mobile nodes in the networks; it is found that the data delivery fraction decreases as the size increases. EAODV-BR delivers more packets, and those packets that are delivered in EAODV-BR but not in AODV-BR, take new routes by reconstruction of the routes. EAODV-BR having longer delays than AODV-BR does not represent its ineffectiveness since these protocols use the same primary route and alternate route Because EAODV-BR and AODV-BR both have the same amount of control message overhead; we used a different metric for efficiency evaluation. We present the number of hop-wise data transmission per data delivery to the destination in Figure-4.9 to Figure-4.12 .We can observe that EAODV-BR transmits slightly more data packets than AODV-BR. The reason being when both primary and alternate route break occurs, EAODV-BR uses reconstruction of route to deliver packets that are dropped in AODV-BR, as explained above.




Every mobile node has an initiated amount of energy. By reducing consumption of energy we can increase the lifetime of the node, so it is desirable to take into account the residual energy. Therefore, it is significant to select a node with residual energy. Residual energy is the available energy after the simulation completed.

Residual Energy is defined as:

Residual Energy = Initial Energy - Energy Consumed

If residual energy is not consider during the routing, than unbalanced node energy consumptions occurs. The unbalanced node energy consumption leads to failure of the nodes as the result of which an interruption in the communication takes place. So it is essential to consider the residual energy in routing protocols.


The proposed protocol performs a route discovery process similar to the AODV protocol. The difference is to determine an optimum route by considering the residual energy of nodes on the path and hop count. In order to implement such functions, a new field known as Min-RE (minimum residual energy) field is added to the route request (RREQ), route reply (RREP) message as well as route list of the nodes. Let us call the proposed protocol AODV_RE.

5.2.1 Message Format for the Proposed Protocol

Message format and route table structure of AODV is modified for the proposed protocol by adding a new field called Min-RE field which contains minimum residual energy of the node. The frame format for RREQ message and route table are given as:









Destination IP Address


Destination Sequence Number

Destination IP Address

Route List

{next hop, hop count, Min-RE }

Destination Sequence Number

Source IP Address

Source Sequence Number


Life Time

Fig. 5.1 AODV_RE RREQ Format Fig.5.2Route Table Format

Writing Services

Essay Writing

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.