Quadrant Directional Routing Protocol In Adhoc Networks Computer Science Essay

Published: Last Edited:


Abstract - A "mobile ad hoc network" (MANET) is an autonomous system of mobile routers connected by wireless links. Routing has been the main challenge in mobile ad hoc network due to infrastructure less and dynamic nature of network topology. One of weakness of mobile ad hoc network is the route between source and destination is likely to break during communication. One of method to identify the destination of mobile node is flooding. Flooding of request packet in the route discovery phase in Mobile Ad Hoc Network creates a broadcast Strom which increase the probability of packet collision. In these papers we implementing Quadrant based directional routing protocol (Q-DIR) algorithm that limits the broadcasting region to a quadrant where the destination node and source node are located. So that we increase Security, latency, throughput and scalability while transferring the packet.

Keywords-Position-based Routing protocol, Restricted flooding, AODVbis, Quadrant-based directional routing, Security.


In our future living environment information will be the most important commodity and exchanging via electronic devices (wired and wireless) and across networks will be a very important factor. Mobile Ad Hoc Network (MANET) is a peer to peer wireless infrastructure less network where communication among nodes can be made and setup almost immediately especially in emergency and disaster operations, military battlefield and even in a building for security and surveillance .

The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the Internet. Multi hop, mobility, large network size combined with device heterogeneity, bandwidth and battery power constrain make the design of adequate routing protocols a major challenge task because of the mobility of nodes. Various routing metrics usually used are shortest path, link stability and minimum number of hops towards the destination. But, recent routing metrics that have been extensively researched are power conservation and optimized bandwidth because mobile nodes in MANET are stand-alone devices and operate on batteries. Routing protocol in MANET can be categorized into topology-based and position-based protocols. In position-based protocol, routing is optimized by making use of geographical information available at each node. The location information of the destination are assume available by a position service while location information of the neighbors are made known through beaconing to all neighbors.

The characteristics of wireless networks differ from wired networks in several ways, caused by their low link capacity and high bit error rates:

ââ‚¬Â¢ Due to small-scale and large-scale channel variation, the channel quality changes within milliseconds depending on the nodeââ‚¬â„¢s location and mobility. The routing protocol cannot select a route simply based on a single route request message.

ââ‚¬Â¢ The wireless link capacity depends on the status of other links in its transmission range. Therefore the congestion can also be caused by the inference of other links.

Because of the direct coupling between the physical layer and the upper layers, the traditional protocol stack is not sufficient for wireless networks.


Application domains for ad-hoc networks include E-learning, vehicular communication collaborative electronic shopping and game playing at a specific place. It is the purpose of this section to identify characteristics and requirements that are common to these and other ad-hoc network services with respect to information disseminate, sharing and retrieving.


With the advent of Global Positioning System (GPS) and MANET environment-based self-positioning and remote-positioning system, location information can be easily disseminated to the requesting node as required in the position-based routing protocol. Only Position-based routing protocols utilizes location information of the destination node to select the node with the best progress as in greedy forwarding or to limit the flooding region based on distance, angle and distance Covered by the next intermediate node. It also requires an up-to-date local topology via periodic beaconing. Hence, the route discovery can be eliminated and only data packet forwarding are employed until it reaches the destination. In this paper, only restricted flooding routing protocols are considered.

A Restricted flooding is a distance from the node to the destination is used to determine nodes participation in the route discovery process. Nodes that are further away from source will not participate. LAR calculates distance from the destination based on location information of the destination that will be extracted from the request packet while uses the relative neighborhood graph (RNG) which together with local information of distance to neighbors and distances between neighbors will minimize the total energy consumption while still maintaining the whole network coverage through broadcasting. LGF calculates distances to all nodes in the network and will compare the distance information of the source to the destination extracted from the request packet to determine its participation. On the other hand, ARP and DREAM uses the angle made from the straight line drawn from source to destination as the restricted region whereby all nodes in this region will participate in the route discovery. However, DDB uses the location information of the destination node and also of the intermediate node which are inserted in the request packet. With this additional information, an intermediate node can calculate the estimated additional covered area that it would cover with its transmission which is based on Dynamic Forwarding Delay (DFD).

The concept of DFD is to determine when to forward the packet and node with more area covered will be given a smaller delay to broadcast and hence, will broadcast it first. All the proposed protocols require computation of the distance and angle at all intermediate nodes to determine the nodes that are located in the forwarding region. Location information of destination node is sent in the request packet as the source node as well.

A. Implementation Environment

Among the reactive protocols that are actively researched and in fact have been upgraded to Recommended for Comments (RFC) in the Internet Engineering Task Force (IETF) are Ad-hoc On-demand Distance Vector (AODV) and Dynamic Source Routing (DSR) . Between them, there are several drawbacks and advantages and work to converge these two protocols are submitted to IETF as an Internet-Draft and are called AODVbis which was based on the work reported. The protocol optimizes AODV to perform effectively in terms of routing overhead and delay during high load. The differences between AODVbis and AODV are path accumulation in the RREQ and RREP packet, more efficient beaconing, adding Originator Sequence Number in RREP and lastly, removal of precursors list. There are two approaches to consider when developing a MANET test bed; kernel environment or the user space. Several test based implementation were developed as reported that shows that developing MANET routing protocol in the kernel reduces the user-kernel crossings inherent in user domain test bed implementation. However, complex mathematical computation in kernel cannot be employed due to the floating point problem. Therefore, considering the mathematical computation constraints by the kernel environment, a simple comparison made on-the fly with the relevant location information extracted from the request packet will be used as proposed in Q-DIR. This information will determine the quadrant both source and destination node are located and intermediate nodes that received this broadcast will compare its location compared to source and destination and then decide to broadcast or not. With restricted flooding based on quadrant, and the path accumulation feature in AODVbis, the number of nodes participating in the route discovery will be reduced and hence reduces the Routing overhead and consequently total power consumption. Figure 1 show the participating nodes if total flooding is employed that will result in the more routing packets being broadcast in the network. On the other hand, if restricted flooding is employed based on the same quadrant an intermediate is located compared to source and destination, less nodes will participate in the routing process which will reduce the number of routing.


A. Quadrant-based Directional Routing Protocol (Q-DIR):

Q-DIR is a restricted flooding routing protocol that concentrates on a specified zone using location information provided by a location service. In Q-DIR operation, the location information of the source and destination nodes is piggy-backed in the route request (RREQ) packet and then broadcasted. Upon receiving the RREQ, intermediate nodes will compare

Fig : Packets that traverse through the network as shown .

Fig 1. Participating nodes in total flooding algorithm.

using a simple mathematical comparison based on the coordinates of source, destination and the current node that directs the packet towards the destination and as illustrated in Figure 3. This mathematical processing will be done in the kernel environment to eliminate the crossover from user to kernel space and vice versa. The decision to participate is made immediately and a neighbors table is not required. Once the decision to broadcast has been made, the Intermediate node will insert its location by replacing the source node coordinates and append its address and sequence number at the end of the RREQ packet. It will then broadcast the packet. The process will repeat at each intermediate node until it reaches the destination. The replacement of the source node location information with the intermediate node coordinates will make the packet more directed towards the destination since the comparison now is based on the previous node. Upon receiving the RREQ, destination node will send a route reply message (RREP) back to source via the path taken to reach the destination that was appended in the RREQ as it traverses across the network. There is no need for the route discovery to the source node. Figure 4 shows the format of the RREQ packet in Q-DIR

Fig. 2. Less participating nodes in Q-DIR algorithm.

where the source and destination nodes location information are inserted are highlighted

Fig. 3. RREQ format in Q-DIR.


Q-DIR was simulated in ns-2 which is a discrete event simulator written in C++ and uses Massachusetts Institute of Technology (MIT) Object Tool Command Language (OTcl) as a command and configuration interface. There is a one to one correspondence between the compiled C++ hierarchy and the interpreted OTcl. Since our work involves routing, we need to develop the algorithm in the compiled C++ hierarchy and compiled it through commands make and make clean in the Linux OS Figure 5 shows a network model of 49 nodes that forms a 7 by 7 grid model where the distance from adjacent nodes are 30m. Based on this grid model, the density is 1 node per 661m2. In the network model, the x- and y-axis of the

Fig. 4. Simulation Network Model of 49 nodes.

Cartesian coordinate system have been drawn to denote in which quadrant the nodes are located. The source and destination are denoted by the letter S and D respectively and destination node is at the top right edge of the grid. Table 1 shows the simulation configuration parameters used in the simulation which conforms to the Internet- Draft [9]. The maximum number of hops between nodes has been set to 10 while the estimated average of one hop traversal time is set to 0.6 s. For correct operation, the route delete period must be greater than both (Allowed HELLO loss* HELLO interval) and the total traversal time.


Configuration Parameters


Maximum number of possible hops between two nodes


Average one hop traversal time


Route discovery time


Route delete period


Number of RREQ tries


Total traversal time


HELLO interval


Allowed HELLO loss


The MAC layer protocol used is IEEE 802.11 DCF CSMA/CA. The data rate has been set to 2 Mbps and the network protocol is IP. The path loss model used is the log-normal path loss model [25]. The receive threshold power is set as 1.20475e-08 watts. The data packet length has been set to 1000 bytes with a CBR (Constant Bit Rate) traffic pattern. Table 2 shows the simulation parameters used in the simulation.



IEEE 802.11b Standard

Propagation Model


Path Loss Exponent


Shadowing Deviation (dB)


Reference Distance (m)


Physical Layer Type


MAC Layer Type


Carrier Sense Threshold


Received Threshold


Default Transmitting Power

2.8318 Watts

Traffic Type

Constant Bit Rate (CBR)


Two scenarios were simulated and they are to study the effect of varying simulation time and effect of varying packet transmission rate. The two protocols that were simulated are AODVbis which is a total flooding protocol and Q-DIR which is based on restricted flooding. The performance metric used: normalized routing overhead -

Fig 6. Normalized routing overhead with simulation time

The number of routing packets transmitted per data packet received at the destination. Effective energy consumption per data packet received - The total energy consumption in the network for every data packet successfully received by the destination. This is the metric on the effectiveness of energy consumption when routing data packets. A Varying Simulation Time The simulation time was varied from 100s to 800s in steps of 100s.

The number of routing packets that are broadcast and the corresponding data packet received at the destination in the network are counted for both AODVbis and Q-DIR routing protocol. Figure 6 shows the normalized routing overhead graphs for both protocols. As the simulation time increases to 800s, both protocols show reduced routing packets and leveled to a constant as it approaches 800s. The average normalized routing overhead in AODVbis is 338 packets while in Q-DIR, the average normalized routing overhead is 128 packets per data packet received. It is observed that 160% more routing packets are transmitted in AODVbis compared to Q-DIR due the higher number of node participations in the network in AODVbis.

Fig 7. Effective energy consumed per data packet received in Q-DIR.

Fig 9. Effective energy consumed per data packet received


This paper has presented the performance of Q-DIR which is a restricted flooding algorithm which uses location information of the source, destination and the intermediate node to determine the broadcasting decision. Nodes that are in the restricted broadcast region will broadcast while other nodes which are out of this region will ignore the RREQ packet. The simple mathematical comparison is implemental in the kernel environment which does not incur processing delay due the crossing from user to kernel space and vice versa. The simulation results shows that implementing Q-DIR reduces the power by 160% as the simulation time is increased and by 45% as the transmission rate increases compared to AODVbis. The restricted flooding and directional routing reduces the number of participating nodes as the RREQ traverses in the network towards the destination node and hence reduced routing overhead and power consumption are achieved in Q-DIR. We have only considered static networks and intend to simulate in mobile environment.