Optimal Route Based Advanced Algorithm using Hot Link Split Multi-Path Routing Algorithm

Published Online July 2014 in MECS

Recently Ad hoc networks are enjoying unprecedented research issues, and are expected to offer opportunities for utilization of network applications in new scenarios in which today Internet-based communication paradigms are not applicable. Generally, ad hoc networks will be formed in situations where no predetermined subnet structure (infrastructure) is available, and for which is known. Ad hoc networks are typically considered to be composed of mobile wireless devices, having rapid change in pathways. This characteristic of Ad hoc network often causes to be viewed more quite different than traditional networks; there are some strong commonality which, as require to learn and understand it better (Elizabeth M, et. al. 2003).

Mobile Ad-Hoc networks (MANETS) are selfconfigured and infrastructure less network with more number of mobile devices connected via a wireless links. [19]. Energy conservation in ad-hoc networks is very important due to the limited energy availability in each wireless node [15]. Ad hoc networks are typically considered to be composed of mobile wireless devices, with the result that the interconnection pathways between the devices can change rapidly. This characteristic often causes ad hoc networks to be viewed more quite different than traditional networks; however, our experience shows that instead there is a strong commonality which, as we learn to understand it better, will illuminate not only the nature of ad hoc networks but also some fundamental aspects of networking [14].

The MANET is the combination of mobile nodes (MN) and wireless communication links. They are connected to each other without the help of access point (AP) and it is shown in Fig. 1. For efficient communication in MANET, the frequent link establishment is mandatory and it has application in disaster area, battle field etc. It requires the routing protocols to establish the connection and route data packets [17].

Fig.1. Ad Hoc Network System Architecture

Multipath routing can be fundamentally more efficient than the currently used single-path routing protocols. It can significantly reduce congestion in “hot spots”, by deviating traffic to unused network resources, thus improving network utilization and providing load balancing [21]. Moreover, congested links usually result in poor performance and high variance. For such circumstances, multipath routing can offer steady and smooth data streams.

In recent years, computer communication networks have developed rapidly. The reason why it develops so rapidly is due to one of the critical technologies—routing technology. For routing packets in the Internet, either a single-path can be used for all the packets from a source to a destination or multiple paths can be utilized. Many different kinds of single path routing, such as Dijkstra algorithm [21], SWP algorithm [22], and WSP algorithm [23] and so on, have been proposed. But according to these methodologies, transit node can only conduct data forward and transmission through single path, which will make message incline to take up nodes and links which have stronger processing capacity. Thereby, it easily leads to link congestion, data packet loss, network throughput reduction, link load unbalanced, which always makes some nodes and links in the state of congestion or overload , but the other in the low state in most times. The secondary paths can be used to transmit data packets, in case the primary path fails due to node mobility or battery failure, which avoids extra node mobility or battery failure, which avoids extra overhead generated by a fresh route discovery.

These multiple paths are more advantageous in larger networks, where he number of route breaks are high.

In a network composed of mobile nodes, changes in the network topology required the frequent rebuilding of routes, so maintaining stable routes may be infeasible. Therefore, MANET is a communication network of a set of mobile nodes, placed together in an ad hoc manner, without any fixed infrastructure that communicate with one another via wireless links. All nodes have routing capabilities and forward data packets for other nodes in multi-hop manner. A Node can enter or leave the network at any time due to its mobility; the network topology continuously changes during deployment. The need for exchange of digital information outside the typical wired office or unarranged environment is growing such as a class of students may need to interact during a lecture; business associates serendipitously meeting in an airport may wish to share files; or disaster recovery personnel may need to coordinate relief information after a hurricane or flood like disasters. The devices used by these information producers and consumers can be considered a node in a MANET [2].

Extensive research works for MANETs are carried out mainly in the fields of Medium Access Control (MAC), routing, resource management, power control, and security issues. MANET Routing Protocols are so important in Dynamic Multi hop Networks, various MANET Routing Protocols have been proposed with several research issues in the last few years. Generally following properties are expected in MANET routing protocols:-

• •    To increase its reliability, a routing protocol for MANET should be distributed in manner in order

• •    By considering power-efficiency as an important feature, a routing protocol must be designed for unidirectional links.

• •    To avoid overhead, a hybrid routing protocol should be much more reactive than proactive

• •    A routing protocol should be having features of Quality of Service (QoS) [12].

• II.    Routing in MANET

Routing is the process of information exchange from one host to the other host in a network by forwarding packets towards its destination using most efficient path among the available in routing. Efficiency of the communication path is measured in various parameters such as number of hops, traffic, security, and energy of nodes etc. In MANET each host node acts as specialized router itself [4].

• A.    Different Strategies

Routing protocol for mobile ad-hoc network (MANET) can be categorized in three strategies.

• •    Flat and Hierarchical architecture.

• •    Pro- active and Re- active routing protocol.

• •    Hybrid protocols.

• B.    Flat Vs. Hierarchical Architecture

Hierarchical network architecture topology consists of multiple layers where top layers are more seen as master of their lower layer nodes. There are cluster of nodes and one gateway node among all clusters has a duty to communicate with the gateway node in other cluster. In this schema there is a clear distribution of task. Burden of storage of network topology is on gateway nodes, where communicating different control message is dependent on cluster nodes.

But this architecture breaks down when there is single node (Gateway node) failure. Gateway node becomes very important for successful operation of network. Examples include Zone-based Hierarchical Link State (ZHLS) routing protocol. In contrast, in flat architecture there is no layering of responsibility.

• C.    Proactive Vs Reactive Routing Protocol in MANET

• •    Proactive Routing Protocol

  In Proactive routing protocol, each node maintains the network topology information in the form of routing tables by periodically exchanging routing information. In the whole network, routing information is generally flooded. Whenever a node needs a route to the destination it runs an appropriate path finding algorithm on the topology information it maintains (Humaira Nishat, et.al. 2011). In a network utilizing a proactive routing protocol, every node maintains one or more tables representing the entire topology of the network. These tables are updated regularly in order to maintain up-to-date routing information from each node to every other node. To maintain the up-to-date routing information, topology information needs to be exchanged between the nodes on a regular basis, leading to relatively high overhead on the network [18].

Current routing protocol such as Link State Routing (LSR) protocol (Open Shortest Path First [20]) and the Distance Vector Routing Protocol (Bellman-Ford algorithm) are not suitable to be used in mobile communication. DSDV (Destination Sequenced Distance Vector Routing protocol) and other wireless routing protocols were proposed to eliminate counting to infinity and looping problems of the distributed Bellman-Ford Algorithm [5]. There are several Proactive Routing Protocols; some of them are:

• •   Global State Routing (GSR)

• •   Hierarchical State Routing (HSR)

• •   Destination Sequenced Distance Vector Routing

(DSDV)

• •   Reactive Routing Protocol

In this type of routing protocol, every node in a network discovers and /or maintains a route based on-demand. It broadcast a control message during discovering a route and when route is discovered then bandwidth is used for data transmission. The main benifit is that this protocol needs less touting information but the disadvantages are that it produces huge control packets due to route discovery during topology changes which occurs frequently in MANETs and it incurs higher latency [4]. Reactive routing protocols are on-demand protocols. These proto-cols do not attempt to maintain correct routing information on all nodes at all times. Routing information is collected only when it is needed, and route determination depends on sending route queries throughout the network. The primary advantage of reactive routing is that the wireless channel is not subject to the routing overhead data for routes that may never be used [18].

Examples of reactive protocols are:

• •    Ad hoc On-demand Distance Vector Routing (AODV).

• •    Dynamic Source Routing (DSR).

• •    Location Aided Routing (LAR).

• •    Temporally Ordered Routing Algorithm (TORA). [5].

• D.    Hybrid Routing Protocols in MANET

These protocols combine the best features of the above two categories. Nodes with a certain distance from the source node concerned or within a particular geographical region are said to be within the routing zone of the given node. A table-driven approach is used for routing within this zone. An on-demand approach is used for nodes located beyond this zone [4].

• III.    Previous HLSMPRA Algorithm

Providing multiple routing paths between any source destination pair of nodes has been proved to be very useful in the context of wired networks. The general understanding is that dividing the flow among a number of paths (instead of using a single path) results in a better balancing of load throughout the network [26] and [27].

In the context of mobile ad hoc networks, several multipath routing protocols have been proposed [26]. The performance of these protocols has been mainly studied through simulations. Recently, some paper have studied different aspects of multi-path routing by providing analytical models .The only know result which studies the distribution of load in an ad hoc network is due to Pham and Perreau. They have introduced an analytic model HLSMPRA algorithm mainly aims at dealing with the degradation of performance in whole networks resulting from rare area congestion in wire transmission network. Firstly, the focus of our work is to keep the routing information in the source node, so as to conduct data transmission in method of alternative path or multi-path inter-currently in source node when congestion happens. Secondly, check congestion regularly, meanwhile record the bandwidth of each link, and then judge whether the link in the state of overload by comparing excess bandwidth [13]. One of the main reasons for the popularity of Dijkstra's Algorithm is that it is one of the most important and useful algorithms available for generating (exact) optimal solutions to a large class of shortest path problems that’s why we are using Dijkstra algorithm here. We can use Dijkstra's algorithm to find the shortest path between any two vertices in a weighted graph, where each edge has non-negative edge weight. Although most applications of shortest path involve graphs with positive edge weights, such a condition is not needed for either Prim's or Kruskal's algorithm to work correctly. The principle behind Dijkstra's algorithm is that given the shortest path between and each of a given set of vertices vlMVb.—vft , there must exist some other vertex x such that the shortest path from to x must go from to VL to x, for some 1 < i

This algorithm mainly aims at dealing with the degradation of performance in whole networks resulting from rare area congestion in wire transmission network. Firstly, the focus of our work is to keep the routing information in the source node, so as to conduct data transmission in method of alternative path or multi-path inter currently in source node when congestion happens. Secondly, check congestion regularly, meanwhile record the bandwidth of each link, and then judge whether the link in the state of overload by comparing excess bandwidth.

• 1.    Call Dijkstra algorithm, to evaluate the shortest path sp between source node and destination node, if set SP is null set, quit, and otherwise continues.

• 2.    Search and compare each path in SP, and do statistics of each link frequency. Range them in order from high to low.

• 3.    For each link in SP, Check the excess bandwidth regularly.

• 4.    Identify from the result which link is heavy load link, and put it into set A; that it’s a idle link, put the links which satisfies the condition into set B.

• 5.    Choose links from the set A, if k=0 stop and otherwise to continue procedure 6.

• 6.    Find out the upstream node w of the heavy link, find out w node in idle set, and select the node link of next hop .Get data packet through the path, make the bigger Bandwidth path of surplus link as the first priority links.

• 7.    After selecting the new path, figure out the surplus bandwidth, and then sort it out and put into corresponding set (set A or set B)

• 8.    If k=0 then do stop calling the algorithm; otherwise, to continue to check the heavy load links, and split stream, then jump into the step 4.

• IV.    Proposed System

In the proposed algorithm, multipath is discovered and maintained in advance at the time of route discovery, but instead of considering each and every RREQ at each node it will consider only specified number of request. At destination or intermediate node, RREP is sent to every received RREQ from unique node. Thus more than one path is maintained all with same but optimal paths will be stored in routing table and one of them will be used for data transfer. Other non used optimal paths will be used at time of link breakage. Three phases of proposed system are Route Discovery, Data Sending and Route Maintenance

• A.    Route Discovery

Route discovery is initiated by the source node when it has some data to send and does not have the route table entry for the destination. It broadcasts RREQ packet to its neighbors.

When Intermediate node gets RREQ, it will check for the route table entry, for the destination mentioned in the RREQ packet. If it finds route table entry for the destination, it will generate RREP packet and send it to the source node otherwise it will rebroadcast the RREQ, after updating the route entry for the source. When RREQ packets come at the destination, it will generate RREP packet for each RREQ packet, and unicast it to the source.

• B.    Data Sending

As soon as the first RREP packet comes to the source data packets data will be sent and it will traverse hop by hop.

• C.    Route Maintenance

If a link break is detected, it will check for the unreachable destination and if any, it will broadcast a Route Error (RERR) packet. The entire node getting RRER packet, will re broadcast it if and only if there is at least one unreachable destination.

As we have alternate optimal paths, when a data packet arrives, it will use the next path which is available. i.e. It switch to the next optimal path on route failure and will send the RERR only when it does not have any alternate path for the destination.

• D.    Proposed Algorithm Procedures:

Start with the estimation of the Delay, Bandwidth, availability, mobility factors for each node.

Identify the routes and validate each route for available packet forwarding/transmitting for selecting optimal path.

Remove the available routes, which is not satisfied the above condition.

Randomly select any one route from the available routes to identify optimal route.

After identifying the optimal route, the packet can sent using optimal route.

• V.    Simulation and experiment

This paper emphasis on the evaluation of performance of Ad Hoc routing protocol AODV with varying the number of mobile nodes. OPNET is used as network simulator in this research work. The network simulator OPNET is discrete event simulation software for network simulations which means it simulates various events for communication with nodes like sending, receiving packets along with forwarding and dropping packets. The version of OPNET is 14.0, supports simulation for routing protocols for ad hoc wireless networks such as AODV, TORA, DSDV, and DSR. OPNET is written in C++ programming language and Object Tool Common Language (OTCL). This software allows nodes and protocols to be modeled as classes with all features of object oriented design to model the behavior of individual objects at the “Process Level” and interconnects them to form devices at the "Node Level" So that you can interconnect devices using links to form networks at the "Network Level" by designing multiple network scenarios into “Projects” to compare designs and Aggregate traffic from LANs or "Cloud" nodes [8].

The OPNET model in its very core consists of C++ codes. These codes are complied and executed just like the C++ program. This enables very detailed control of the model by the user (if the user is proficient in C++). The package consists of a number of tools, each one focusing on particular aspects of the modeling task. These tools fall into three major categories that correspond to the three phases of modeling and simulation projects: Specification, Data Collection and Simulation, and Analysis [16].

The OPNET usability can be divided into four main steps. The OPNET first step is the modeling, it means to create network model. The sec step is to choose and select statistics. Third step is to simulate the network. Fourth and last step is to view and analyze results. All these steps are shown schematically in the below Fig. 1.To build a network model the workflow centers on the Project Editor. This is used to create network models, collect statistics directly from each network object or from the network as a hole, execute a simulation and view results.

Fig.2: Flow chart of OPNET

• A.    Simulation Parameters

  The performance of AODV protocol is evaluated by keeping the network speed and pause time constant and varying the network size (number of mobile nodes) in the network scenario where nodes are placing within a 1000 m X 1000 m area. Simulation parameters used in this research work are listed in table 1.

Table 1: Simulation Parameter

Parameters	Values
Simulator	Opnet-14.0
Protocol	AODV
Simulation Duration	30 min
Number of nodes	13
Pause Time	100sec
Average Speed	102.714 events/sec
Addressing Mode	IPv4
Packet Size(bits)	1024
Data Rate(bps)	11mbps
Buffer Size(bits)	256000

• B.    Performance Metrics

This research work concentrates on 3 Performance metrics which are End to End Delay, Routing Load, and Total route error sent to analyze the AODV protocol. The graphs drawn in Fig. 1 to 4 shows that the overall performance- End to End Delay, normalized routing load, Packet Drop and Total route error sent are improved by using our local route repair method.

End-to-End Delay: A specific packet is transmitting from source to destination and calculates the difference between send times and received times. In the delay metric, the delays due to various situations like route discovery process, queuing method, propagation delay and packet transfer time are included.

Routing Load: The number of routing packets transmitted per data packet delivered at the destination node. Every hop wise transmission of a routing packet is counted as one transmission.

Total Packet Drop: There may be a chance of loss of packets in wireless communication, due to some error in transmission. Losses in packet may occur because of the mobility of the nodes. Mobility also induces route change in the network which is tolerable but packet loss is not tolerable for effective communication.

Total Route error sent: In routing protocols the nodes generates error packets when the route is broken or interrupted. These packets are diffused to nearby nodes which are affected due to route break. The total number of routing packets transmitted during the simulation.

While analyzing the proposed system with HSLMPRA, we have also focused on the following performance metrics which are Media Access Delay, Retransmission Attempt and Network Load -

Retransmission Attempts (Packets): It is the total number of retransmission attempts by all WLAN in the network until either packet is successfully transmitted or it is discarded as a result of reaching short or long retry limit.

Media Access Delay (sec): It represents the global statistic for the total of queuing and contention delays of the data, management, delayed Block-ACK and BlockACK Request frames transmitted by all WLAN MACs in the network.

Network Load: When there is more traffic coming on the network, and it is difficult for the network to handle all this traffic so it is called the network load.

• C.    Simulation Environment

Here simulation is carried out in the OPNET Modeler 14.0. Below in Fig. 3 shows the simulation environment of one scenario having 13 mobile nodes.

• VI.    Simulation and Results

Fig.4. Total Delay

Fig.5: Routing Load

Fig.6: Total Packet Drop

In this paper, local retransmission is used to improve the End to End Delay. Improved Delay, Routing Load denotes the efficiency, reliability and effectiveness of proposed routing protocol. Thus, the total route error is reduced to some extent. Though it is expected to produce minimum error sent for the proposed routing Algorithm; Total Delay is an indication of reliability, efficiency, and effectiveness of routing protocol. From Fig. 4, the Total Delay shows improved reliability, effectiveness and efficiency.

Fig. 5 shows Routing Load, Fig. 6 shows total packet Drop and Fig.7 shows total route error sent.

Fig.7: Total Route Error Sent

• VII.    Conclusions

The proposed algorithm will generate slightly higher overhead than that of Previous Algorithm for first time at the time of route discovery. Our mechanism setups multiple optimal paths based on bandwidth and delay. It allows storing multiple optimal paths based on Bandwidth and delay. At time of link failure, it will switch to next available path. But once route discovery is over, it will be beneficial for route maintenance. And this overhead overcomes the route overhead generated at the time of link failure. The proposed Algorithm reduces the total Delay, Routing Load, Packet Drop, Total route error sent. This algorithm is based on Optimization. The proposed algorithm improves the efficiency, robustness and reliability. The efficiency of proposed Algorithm was shown to better than Previous Algorithm.