24-09-2016, 10:35 AM
1455984194-7610400761504.044201.docx (Size: 730.53 KB / Downloads: 3)
ABSTRACT
During route discovery of mobile ad hoc network, broadcasting of route request and route reply packets are the essential operations for finding the path between two ends. In such situations, intermediate node which may or may not belongs will participate in route discovery process, update routing table and rebroadcast the route discovery packets again to its neighboring nodes. Finally optimal path is found with minimum hops. This simply upsurges overhead and deteriorates the performance of routing. The proposed Petal Ant Routing (PAR) algorithm offers a low overhead by optimizing FANT and BANT transmissions in route discover process. The algorithm is an improved version of SARA and has features extracted from petal routing. The algorithm is simulated on NS2, compared with ACO frame work called SARA and classical routing protocols such as AODV and AOMDV. The simulation results shows that PAR further reduces overhead by eliminating redundant FANT transmission compared to other routing algorithm.
INTRODUCTION
A mobile ad hoc network (MANET) [1] is a network consisting of a set of mobile nodes with no centralized administration. MANET is self-configuring, self-organizing and self-maintaining. MANET may have dynamic topology. Mobile ad hoc network (MANETs) [1] [2] are special kind of infrastructure less wireless ad hoc network. In Manets, each node acts as router and a host at the same time which joins and leave network at any movement of time with high mobility [3]. Due to nodes high mobility, the topology of the network is subject to change frequently and routing for such a situation becomes difficult. The design of mobile ad hoc routing protocols is extremely challenging task because of limited bandwidth, limited power, and unpredictable radio channel behavior and node mobility [4]. The main challenges of routing protocols for Manets are to ensure that nodes are able to select an optimal path to forward the data traffic from source to the intended destination. Many routing protocols have been proposed for routing issues such as AODV [5], AOMDV[6], DSR[7], DSDV [8], TOHIP [9], S-AODV [10], S-DSDV [21],...etc, but many researchers have stated in literature that the Ant have the better potential to find an efficient and shortest path much optimal than other routing algorithm b y depositing chemical substance called pheromone [2 indexing]. The researchers observed the behaviour of real ants and inspired to design a new ant routing protocols for manet such as ACO[11], ARA[12], SARA[13], HOPNET[14], ANTnet [15], Ant AODV [16], ANTALG [17], etc. In popular population-based meta-heuristic ACO algorithm, when source requires a path to destination, source broadcast special kind of packet called Forward Ant [FANT] to its neighbor nodes, which replicates and rebroadcast the FANT until it reaches destination. The destination node then destroys the FANT and reply with special packet called Backward Ant [BANT] through the intermediate nodes. Upon the reception of BANT, the source starts sending data to the destination through the shortest path. But in SARA [13], it works with the mechanism called Controlled Neighbor Broadcast [CNB], in which every node broadcast FANT to its neighbor but only one of them rebroadcast again to its neighboring node. According to author [13] [18] since FANT packet replicated by all network nodes and the network is flooded with control information will reduce its performance. Figure 1 illustrates the FANT propagation of Ant routing algorithms. As the network grows large, the large number of network nodes joins in FANT and BANT transmission which significantly increases overhead and deteriorates its performance [13]. The flooding mechanism of this FANT and BANT transmission in the network is the disadvantage and increases the time required to discovering route during route discovery [13]. The aim of all routing protocols for data transmission is to find shortest path and optimal path between end nodes, but even though a network is loaded with large number of nodes, all most all routing protocols chooses minimum hops for establishing a shortest path between source and destination and eliminates all other nodes during route discovery. So flooding FANT packets for all redundant nodes during route discovery significantly increases additional time to update routing table and increases overheads. Hence, the aim of our proposed work is to minimize FANT transmission during route discovery and to reduce overhead.
The remaining part of this research article is organized as follows. Section 2 describes the literature survey. Section 3 presents the proposed work. Section 4 presents the Simulation results and comparison. Finally conclusion, Appendix and acknowledgement is described at the end of the report.
2. LITERATURE SURVEY
Fernando Correia, Teresa Vazao [13] proposed an improved version of ACO framework called Simple Ant Routing Algorithm (SARA) for the mobile ad hoc network. SARA uses the concept of Controlled Neighbor broadcast (CNB) mechanism to control packet flooding during route establishment and uses deep search procedure to recover route during route repair.
Petal routing [19] is a routing algorithm for MANET. In this routing approach it merge the concept of multipath and geographic routing algorithm, where network nodes are addressed based on geographic location rather than IP address with no routing principle. All the data packets are flooded in the network but the nodes which lies inside the petal region will rebroadcast again to its neighboring nodes.
3. PETAL ANT ROUTING (PAR) ALGORITHM FOR MOBILE AD HOC NETWORK
In this section, we present details of PAR architecture constructs as similar to others routing algorithm. PAR algorithm is an improved version of Simple Ant Routing Algorithm (SARA)[13] and combines the few characteristics of Petal routing [19]. PAR consists of 3 phases namely Route discovers, Route maintenance and Route repair.
. Route Discovery
In the route discovery phase, PAR computes the width of the petal (Pw), create new routes by forwarding special packet called Petal Forward Ant [P _FANT] by source and Petal Backward Ant [B_FANT] by the destination. A P_FANT is a small packet consists of Pw and unique sequence number. One key aspect of this process is to compute the petal region between end nodes and to rebroadcast the P _FANT is describes next. With this, it is possible to minimize the overhead by eliminating redundant P_FANT and P_BANT transmission during route discovery. Thus maximize the ratio of packets generation and minimize the overhead. Consider the Figure 2, Source denoted as S(xs ,ys), Destination D(xd, yd) and the intermediate node i(xi, yi) where i =
1,2,3,..,n. Our proposed work merges the concepts of geographic routing [20].The (x, y)
coordinate of a mobile node represents (longitude, latitude) respectively. Each node is uniquel y addressed inside or outside petal by geographic locations and by node id. When source (S) requires a path to destination (D), source computes the Pw by following 3 steps.
Step 1: obtain nodes location dynamically and compute the distance (d) from S and D using (1)
22 (1)
d xd xs
yd ys
Step 2: Compute and obtain (h, k) using (2)
h = (xs + xd)/2, k = (ys + yd)/2
. Route Repair
The PAR initiate route repair process when broken link between two nodes is detected. Since the nodes are highly dynamic and mobile in nature, the broken link state can happen at any interval of time. This may due to node being turned off, or by limited band width or by congestion occurred, or by pheromone evaporation during data transmission. To repair route, PAR find alternative link in its routing table of the broken link. If there exists any other link between source and destination its sends the packet via this path else, if the route repair procedure fails during searching an alternative path to destination, source initiate a new route discovery process upon the reception error message.
4. SIMULATION EXPERIMENT SETUP USING NS2
The simulation experiment is carried under Ubuntu Linux. The proposed work and SARA of Fernando Correia et.al [NS2 version 2.31] were implemented in NS2 version 2.35 by the author’s. Comparison with classical routing such as AODV and AOMDV of NS2 package is also provided. NS2 implementation of SARA code has been enhanced to reduce overhead by eliminating redundant FANT transmission during route discovery process. The simulation is carried for two different environment (simulation environment A, simulation environment B)