Abstract: The advancement in computing technology has led to the design, development and deployment of high end portable computing devices. These devices are free to move along with their users. Due to their mobility these devices are designed to share the information through temporary networks which don't require much of infrastructure. The ad hoc network is one such network, which can even be deployed in war hit or disaster hit areas where the basic infrastructure facilities such as power network or communication network are destroyed. In the ad hoc network, the data transmission is through intermediate nodes to save the power and every participating node has to work as the router as well. This feature of ad hoc networks has led to the enormous possible routing algorithm design. The basic criteria for efficiency of a routing algorithm include high throughput, minimum routing overhead, path optimality, minimum average delay and minimum packet lost. The literature of ad hoc network contains many routing algorithms, some of these are proactive and others are reactive with each having its own merits and demerits. In such a scenario, hybrid routing can take advantages of both. This paper presents an efficient hybrid routing algorithm.
Keywords: Ad hoc Networks, Routing Protocols.
Introduction
W The origination of Mobile Ad hoc Networks (MANET) from packet radio network (PRNET) [1] and SURAN project [2] has not only rendered the mobile and wireless networks important but the design of an efficient and portable routing protocol a challenging task for the researchers. While designing a routing protocol a designer has to keep in mind the following performance metrics [5]:
Throughput: Defined as total number of packets received by the destination.
Routing overhead: The ratio between the total numbers of routing packets transmitted to the total number of data packets.
Path optimality: The difference between the number of hops a packet takes to reach its destination and the length of the shortest path that physically existed.
Packets lost: Measure of the number of packets dropped by the routers due to various reasons.
Average Delay: Average amount of time taken by a packet to go from source to destination.
A critical aspect involved in the design of ad hoc routing protocol is to ensure the use of minimum power as the devices involved are battery driven and power constrained especially when deployed in the disaster hit area or in war situation where [3, 4, 5] there are no infrastructural facilities. The metrics such as packets lost, high average delay and path optimality are directly related to the power consumption. These aspects of the network can be improved by minimizing the number of collisions [6], reducing congestion and by optimizing the hop count [7, 8]. Thus the basic goal of the routing protocol is to increase the throughput of the network with minimum usage of power.
The paper has been divided in five sections. The Section 2 constitutes literature survey. Section 3 constitutes the details of the proposed protocol. Section 4 provides the simulation results. The paper completes with conclusion and future scope.
LITERATURE SURVEY
The routing protocols can be classified into three categories proactive, reactive and hybrid routing. A proactive routing is also called as table driven routing because in this each node has to maintain routing tables. The tables are updated periodically or on demand basis so as to have complete topological structure of the network. Therefore, a source node can get routing path immediately when it requires. Most proactive routing protocols have inherited properties of wired routing protocols so there are certain limitations such as high control overhead, the scalability is poor but there lies the advantage of using these routing schemes that the time complexity involved in searching the route to the destination is O(1). Reactive routing is also called as on demand routing as the routes are formed whenever there is a requirement. A route discovery operation invokes a route-determination procedure. The discovery procedure terminates either when a route has been found or no route is available after examination for all route permutations. This involves certain delay in routing the data packets. Though the scheme has delay while routing but the control overhead is quite low and scalability is quite good when compared with proactive routing schemes. Hybrid routing protocols can be designed to derive the merits of both proactive and reactive routing protocols and avoid their shortcomings. For example, a hybrid routing protocol such as ZRP assumes hierarchical network architectures with proactive routing approach for intra domain routing and reactive routing approach for inter domain routing. The merit of ZRP hybrid protocol is the reduced control overhead of as compared to proactive routing approaches and the reduced latency as compared to route search operations in reactive routing approaches.
2.1 Table driven routing protocol (proactive routing)
T In table driven routing protocols the nodes maintains routing table to store paths for each possible destination. The tables are continuously updated by message passing techniques. The updates can be periodic or on demand that is when a change occurs in the network. The popular routing protocols in this category are Wireless Routing Protocol (WRP) [10], Destination Sequence Distance Vector (DSDV) [11], and Fisheye State Routing (FSR) [12] etc. The proactive routing is being described with the help of DSDV. The DSDV protocol [11] is similar to WRP but its routing mechanism is quite different. In routing tables of DSDV, an entry stores the next hop towards a destination, the cost metric for the routing path to the destination and a destination sequence number that is created by the destination. Sequence numbers are used in DSDV to distinguish stale routes from fresh ones and avoid formation of route loops. To reduce the overhead of control packet incremental updates along with full dump updates are used. The incremental updates are used when there are minor changes in the topology or when the network is less mobile and full dump updates are sent when ever there are major changes in the topology or the network is mobile.
Disadvantages
Memory requirement: The need to maintain routing tables results in a large memory requirement
Bandwidth requirement: Though it uses incremental updates to reduce the routing messages but still the number of routing messages exchanged is quite large resulting in high bandwidth requirement.
Scalability: The table driven routing protocols are not easy to scale. The scalability is quite poor.
2.2 On Demand routing protocol (Reactive routing)
Reactive routing protocols for mobile ad hoc networks are also called "on-demand" routing protocols. In a reactive routing protocol, routing paths are searched only when needed. A route discovery operation invokes a route-determination procedure. The discovery procedure terminates either when a route has been found or no route available after examination for all route permutations. The popular routing protocols in this category are Ad hoc On Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR) [14], and Temporally Ordered Routing Algorithm (TORA) [18, 19]. The basic operation of on demand routing is explained with the help of AODV. In AODV [13], routing information is maintained in routing tables at nodes. Every mobile node keeps a next-hop routing table, which contains the destinations to which it currently has a route. A routing table entry expires if it has not been used or reactivated for a pre-specified expiration time. In AODV if a source node wants to send a packet to the destination node then firstly it starts route discovery process in which a route request packet is broadcasted by the source node. The route request packet contains the following information
Source node id
Destination node id
Sequence number
When this packet reaches to a node it records originator information as well as from whom the packet is sent to it in its route cache. The node process the route request only if it has not seen this RREQ previously and this is how the loop formation is avoided. The process of broadcasting continues till the RREQ reaches to the destination node or to a node which has information about the destination node in its route cache. After the route request phase the route reply packet is generated using the same path as selected in case of route request path selected.
As shown in the above Fig. 1a the source node (S) broadcast route request to all the neighboring nodes 1, 2, and 4 which in turn broadcast the route request to all their neighboring nodes. The process goes until the packet reaches to the destination node (D). The route request packet reaches the destination from different paths but the path from which the packet reaches first is selected for route acknowledgement as shown in the Fig. 1b.
Disadvantage: AODV does not support unidirectional and multiple routing paths as supported by DSR.
2.3 Hybrid Routing Protocols
Hybrid routing protocols are proposed to combine the merits of both proactive and reactive routing protocols and overcome their shortcomings. Normally, hybrid routing protocols for mobile ad hoc networks exploit hierarchical network architectures. Proper proactive routing approach and reactive routing approach are exploited in different hierarchical levels, respectively. The protocols that fall in this category are Zone Routing Protocol (ZRP) [15], The Zone-based Hierarchical Link State routing (ZHLS) [20], and the Hybrid Ad Hoc Routing Protocol (HARP) [21]. The hybrid protocols are explained with the help of ZRP. In ZRP, the network is divided into routing zones according to distances between mobile nodes. Given a hop distance d and a node N, all nodes within hop distance at most d from N belong to the routing zone of N. Peripheral nodes of N are N's neighboring nodes in its routing zone which are exactly d hops away from N. In ZRP, different routing approaches are exploited for inter-zone and intra-zone packets. The proactive routing approach, i.e., the Intra-zone Routing protocol (IARP), is used inside routing zones and the reactive Inter-zone Routing Protocol (IERP) is used between routing zones, respectively. The IARP maintains link state information for nodes within specified distance d. Therefore, if the source and destination nodes are in the same routing zone, a route can be available immediately. Most of the existing proactive routing schemes can be used as the IARP for ZRP. The IERP reactively initiates a route discovery when the source node and the destination are residing in different zones. The route discovery in IERP is similar to DSR with the exception that route requests are propagated via peripheral nodes.
The hybrid protocols are proposed to reduce the control overhead of proactive routing approaches
Decrease in the latency caused by route search operations in comparison with reactive routing approach..
THE PROPOSED PROTOCOL
To understand the working of the proposed protocol, familiarity with the basic packets and tables involved is necessary. Therefore, we start this section with the brief introduction about these aspects.
3.1 Data Packet Format
This packet is used for exchange of data between the mobile nodes. The basic format of data packet header is given in Fig. 2 Each data packet header will have several fields like packet type, source address of the node that initiates the packet, destination address of the node to which the packet must finally be handed over, a list of addresses of previously visited nodes and hop count indicating the no. of intermediate nodes in the path.
Packet
Type
Source Address
Destination
Address
Visited
Nodes
Hop count
Data
Figure 2 Format of data packet header
Packet Type: identifies the type of packet
Source Address: denotes the address of source that initiates the packet
Destination Address: denotes the address of node that finally receives the packet
Visited nodes: List of intermediate nodes
Hop count: total number of intermediate nodes
Data: data to be sent to the destination (payload)
3.2 Nodes Gateway Table (NGT)
Each node in the network maintains information about its neighboring nodes by broadcasting a hello request and receiving a reply packet in turn. Fig. 3 shows a representative ad hoc network in which each node has been shown connected to its neighbors with the help of dotted lines. The Table 1 shows the different nodes in the network with the list of their neighbors.
Node
Neighboring Nodes
1
3
4
7
2
2
1
7
3
3
4
5
6
1
2
7
4
1
3
5
6
7
8
9
5
3
4
6
6
3
4
5
7
1
2
3
4
8
9
8
7
9
4
9
8
7
4
Table 1 Neighboring Node Information
Thereafter, every node multicasts a Gateway request packet to its neighbors listed in the neighbor table to determine the best first intermediate node its communicate with the rest of the nodes in the network except for immediate neighbors. We name such a node as the gateway node as it acts as the gateway for the node (under consideration) to communicate with rest of the network. For example, according to the Table 1, Node 1 will multicast gateway request packets to nodes 3,4,7,2 (see Fig. 5) to find its gateway for rest of the network barring the immediate neighbors 3, 4, 7 and 2. However, there is no need to search gateway if the destination node is next neighbor i.e 3, 4, 7, or 2. Similar process is repeated by the other nodes to search for their gateway. Fig. 4 shows the basic design of Gateway Request Packet.
Packet
Type
Source
Address
Destination
Address
Figure.4 Gateway request packet
Packet type: identifies the type of packet
Source Address: denotes the address of source that initiates the packet
Destination Address: denotes the address of node that finally receives the packet
Where packet type identifies the packet as a gateway request packet, source address contains the address of the sender node and destination address contains the broadcast address.
Gateway Request packet
Node 1
Node 3
Figure 5 Gateway request packet of node 1 for node 3
Packet
Type
Source
Address
Destination
Address
List of NeighborsWhen a gateway request packet is received by a node, it sends a gateway reply packet to the sender node in the format as shown in Fig. 6a.
Figure 6a Gateway Reply packet
The Fig. 6b shows the Node 3 gateway reply packet when it receives gateway request packet from its neighbors.
Gateway Reply packet
Node 3
Node 1
4,5,6,1,2,7Figure 6b Gateway Reply packet of node 3
After getting complete neighbor list from the neighboring nodes, the node compares this list with its neighboring node list and creates gateway priority table according to the rule that a node with highest new nodes information in comparison to the source node neighbor table is selected as the best gateway. The process of searching the new node information with all the neighboring nodes is continued till a sorted gateway list is created. The process can be made clearer with the help of Table 2.
The node 4 has four new nodes information in comparison to node 1 so it is given the first gateway priority.
The node 3 and 7 has only two new nodes information in comparison to 1 so both of them should have same priority but the node 3 has been given higher priority on the basis of serial number.
The node 1 has four neighbors 3, 4, 7, 2 while the node 2 has three neighbors 1, 7, 3 there is no new node information for node 1 so it is given the lowest priority.
Table 2 Gateway priority table of node 1
Node
Neighboring Nodes
Gateway priority
1
3
4
7
2
2
1
7
3
4
3
4
5
6
1
2
7
2
4
1
3
5
6
7
8
9
1
7
1
2
3
4
8
9
3
It may be noted that every node creates a table called Nodes Gateway Table. The entries of neighboring nodes in NGT are stored in accordance with decreasing value of gateway priority as shown in Table 3 for node 1.
Table 3 NGT of node 1
Nodes
Nodes gateway table
1
4
7
3
2
The nodes in the ad-hoc network repeat the process of gathering the NGT (Nodes Gateway Table) entries in the table until every node has details about their neighboring nodes.
3.3 Algorithmic Details
To initiate or forward data packets the nodes use information contained in NGT table. Whenever due to mobility of nodes there is a packet loss, the NGT entries are updated. However, after a regular interval of time, every node within a cell retransmits a gateway Request packet in order to update the network information. This process helps nodes in acting as per the latest network topology.
The Proposed Routing Algorithm
Dp.hop_count=16;
If (DP.hop_count <1)
Drop the packet /* DP has to be retransmitted from the source of DP
else
{
if( DP.Dest_Addr.== Node Address )
{
Consume the data packet;
}
else
{
DP.hop_count -- ;
Best Gateway selection ();
}
}
The algorithm says that, initially the hop count is set to 16 and when the hop count becomes less then 1 the data packet has again to be retransmitted and if the count is greater then 1 the data packet will call the gateway selection algorithm, which is discussed, in the next section.
Best Gateway Selection Algorithm
Best Gateway selection ( )
{
i=1;
while(sort_gate_list!=null)
{
if (sort_gate_list[I]==visited node)
/*If the Ith entry of the sorted gateway list
Matches with the visited node if yes then
there is no need to visit it again*/
{
i++; /* check the next entry of the
Visited node*/
}
else
{
Unicast the packet to that sort_gate_list[i];
/* deliver the packet to the best gateway*/
exit( )_;
}
}
if all the nodes are visited
{
Set i=1;
Select sort_gate_list [i];
}
}
Simulation Results
A simulator was designed in C++ in which an area of 35*35 sq. unit's size was chosen (see Fig. 7). The nodes were distributed randomly in the given area and following performance metrics [16] results were recorded in an output file
1. Average Power left per node
2. Average Throughput
3. Average no. of hop count for successful transmission
4. Average no. of retransmission required
The following assumptions were made while measuring the above mentioned parameters
1. Antennas are Omni directional
2. Sleep mode power dissipation has been considered as null
3. Mobility has not been taken into consideration
The following assumptions were made in measuring average power:
1. The node looses 2 units battery in transmitting a packet
2. The node looses 1.5 units of its battery power while receiving
Initially each node was given 100 units of power. The simulator designed selects random source and destination every run. Each execution of program involved 20 runs. The average power left per node after all the 20 execution was recorded in an output file as shown in Fig 8.
Figure 8 Battery status after 20 transmissions for different transmission radius
The Average throughput increases as the transmission range increases due to the fact that with increase in transmission radius neighboring nodes get increased (see Fig. 9) resulting in higher probability for a data packet to reach to its destination within permissible hop count.
Figure 9 Average Throughput for different transmission radius
The average number of intermediate nodes that a packet takes to reach to its destination for successful transmission is shown in Fig. 10. As seen in the graph the average number of hops are fewer at lower transmission range since the number of neighboring nodes is quite less as well as the average throughput is also very low. As the transmission range is increased the average numbers of hops for successful transmission increases since the number of neighboring nodes gets increased as well as the throughput also get increased as shown in Fig. 10.
Figure 10 Average numbers of intermediate hops for different transmission radius
The average number of retransmission decreases as the transmission range increases as shown in the graph since as the transmission range increases the number of neighbor gets increased and the probability to reach to the destination also gets increased (see Fig. 11).
0
0.5
1
1.5
2
2.5
3
5
7
9
11
13
Transmission Range
Average Number of retransmission
N=20
N=25
N=30
Figure 11 Average Retransmission for different transmission radius
Conclusion and Future Scope
The proposed routing protocol tries to select the node with highest available gateway priority. The advantage of this protocol is its heuristic approach to find the route. The proposed approach uses both proactive and reactive counterparts for route discovery thereby utilizing the advantages of both. Most of the transmissions used for finding the route involve multicasting which is in contrast to the AODV, which use blind search and major portion of the signals in route finding process involves broadcasting. This leads to major saving of the energy.
As described earlier, the proposed protocol has been implemented in isolation by designing a simulator in C++. Depending upon the requirement the proposed protocol can be implemented on simulators like NS2 or Qualnet and be compared with other existing protocols in the similar conditions as per the requirement. The readers can ask for the C++ code by contacting the authors.
