A Novel Approach for Improving the Performance of Geographic Routing in MANET using OGRP

A Novel Approach for Improving the Performance of Geographic Routing in MANET using OGRP

Prof. Manoj T. Joy, Faculty

Department of Computer Science and Engineering Amal Jyothi College of Engineering

Kottayam, India.

Jenny Elizabeth John, PG Scholar

Department of Computer Science and Engineering Amal Jyothi College of Engineering

Kottayam, India

Abstract In geographic routing, for making effectual forwarding decision, nodes require retaining up-to-date position of their immediate neighbors. A common approach used by most geographic routing protocols to retain their neighbor position is periodic broadcasting of beacon packets. These beacon packets include the geographic location of the nodes. It can be found that periodic beaconing in geographic routing increases the routing overhead and also reduces the network throughput. Another problem found is that a large transmission range and too small transmission range also reduces the performance. So a novel approach is proposed to solve these problems, which includes the Optimum Transmission Range and Adaptive Position Update (APU). Optimum transmission range finds an optimum radio transmission range for every node in the network, by using the single transmission distance energy efficiency. APU includes two rules, first one reduces the beacon overhead due to periodic beaconing and the second one allows the nodes that are involved in data forwarding to improve their local topology. The theoretical examinations are validated by using NS2 simulations of a geographic routing protocol, On- Demand Geographic Routing Protocol (OGRP), shows that APU with optimum transmission range can considerably reduce the routing overhead and improves the network performance and packet delivery ratio.

Keyword-Geographic Routing Protocols; Optimum Transmission Range; Location System; OGRP

1. INTRODUCTION

   With the increasing popularity of positioning devices geographic routing protocols are becoming an attractive choice for use in mobile ad hoc network [1], [5], [6]. The underlying principle used in these protocols involves selecting the next routing hop from among a nodes neighbors, which is geographically closest to the destination. In these protocols it is essential to create and maintain routes for every destination because the forwarding decision is completely based on local knowledge. Due to these advantages geographic routing protocols are very scalable and especially robust to the recurrent changes in the network topology. The forwarding strategy used in the above

   mentioned geographic routing protocol needs two information. First one is the position of the packet`s final destination and the second one is the position of a nodes neighbor. Using Grid Location System (GLS)

   [7] or Quorum [8], the position of the final destination of the packet can be obtained. To obtain the position of nodes neighbors, each node exchange its own position with its neighboring nodes. This helps each node to build a local topology.

   In ad hoc network nodes need to relay on multi-hop transmission when two communicating nodes are not in the range. Routing or packet forwarding becomes necessary in such conditions. Network topology and energy consumption is considerably affected by the value of radio transmission range. The distance progress of data packets toward their final destinations will increase when the transmission range is too high. This can only be achieved at the expense of higher energy consumption per transmission. However, a shorter transmission range uses less energy to forward packets to the next hop, although a larger number of hops are needed for packet to reach their destinations. So an optimum transmission range is needed to solve these problems.

2. EXISTING SYSTEM

   In geographic routing, the forwarding decision at each node is based on the locations of the nodes one-hop neighbors and location of the packet destination as well. Some geographic routing schemes, e.g., [11], [12], simply assume that a forwarding node knows the location of its neighbors. Whereas others exchange neighbors location using periodical beacon broadcasting. In periodic beaconing, the idea is that, with a fixed beacon interval each node broadcasts a beacon to update this position. If a node does not hear any beacon from a neighbor for a certain time interval, called neighbor time-out interval, the node considers this neighbor has moved out of the radio range and removes the outdated neighbor from its neighbor list. The neighbor time-out interval often is multiple times of the beacon interval.

   In highly mobile ad-hoc networks the periodic beaconing

   [13] leads to performances degradation and can also cause inaccurate local topologies. It may result frequent packet loss and longer delay. The major source that decreases the Performance is the outdated entries in the neighbor list. So several proposed including distance-based beaconing (DB), speed-based beaconing and reactive beaconing. The following schemes are discussed below.

   In the distance-based beaconing, a node transmits a beacon when it has moved a given distance d. The node removes an outdated neighbor if the node does not hear any beacons from the neighbor while the node has moved more than k- times the distance d, or after a maximum time out of 5 s. Therefore this method is adaptive to the node mobility. On the other hand this approach has two problems. First, since the neighbor time-out interval at the slow node is longer, the node may have many outdated neighbors in its neighbor list. Second, due to the infrequent beaconing of the slow node, the fast node may not detect the slow node. Which degrade the observed network connectivity.

   Fig.1. Example of Relaying Nodes

   In the speed-based beaconing, the beacon interval is dependent on the node speed. A node determines its beacon interval from a predefined range [a, b] with the exact value chosen being inversely proportional to its speed. The neighbor time-out interval of a node is a multiple k of its beacon interval. Neighbor time-out interval is piggyback with the beacons. The receiving node selects a smaller time-out interval by comparing the piggybacked time-out interval from the last beacon with its own time-out interval. Therefore it eliminate the first problem addressed in the distance based beaconing, that is a slow node can have short time-out interval for its fast neighbor. On the other hand, the speed-based beaconing even now experience the difficulty that a fast node may not detect the slow nodes.

   In reactive beaconing, the beacon generation is triggered by data packet transmissions. When a node has a packet to transmit, the node first broadcasts a beacon request packet. The neighbors overhearing the request packet respond with beacons. Thus, the node can build an accurate local topology before the data transmission. But this method leads to excessive beacon broadcasts, especially when the traffic load in the network is high.

3. PROPOSED SYSTEM

   Enhancing the Performance of Geographic Routing Protocol

   To improve the performance of Geographic Routing Protocol two methods have been used. First one is the optimum transmission range and the other one is Adaptive Position Update.

   1. Optimum Transmission Range

      In the initial phase before the deployment of nodes, then an optimum transmission range is calculated for each node. In this energy consumption for a single transmission is analyzed first then average single transmission distance energy efficiency will find out.

      Calculating Optimum Transmission Range

      In thi paper it is analyzed and optimized that the distance energy efficiency with randomly allocated nodes at the time of the initial transmission, even though a multi-hop transmission is consequently needed for the transmitted packet to reach its final destination. Particularly the single transmission distance energy efficiency is defined as the ratio of transmitted packet`s average progress throughout the initial transmission and the energy consumption of single transmission.

      Energy Consumption of a Single Transmission

      The energy consumption equivalent to every transmission can be calculated as:

      + 1 +2 (1)

      Where r is the radio transmission range, is the path loss exponent, 1 is the characteristic of transmitter and channel, 2 is the energy consumption of the transceiver. Let be the energy consumption of receiving decoding and preprocessing data packet at receiver. For a given r, the fixed single-transmission energy consumed is given by

      +

      Distance Energy Efficiency for Single Transmission

      Fig.1, shows distance between the source node Sr and destination Dt is denoted by u. When (ur), the packet can be transmitted directly to the destination Dt. So the transmitted packet`s distance progress to the destination is

      u. If u> r the source node Sr has to find a suitable neighbor for successive packet routing. Distance progress can be defined as the change in the original distance between the source and destination and the distance between the relaying node and the destination. Therefore the distance progress of the transmitted packet towards the destination node Dt is equal to u-v, where v is the distance between the first hop router X and the destination node Dt.

      The single transmission distance-energy efficiency e(r) is then given by:

      3 2 36 . 1( , , )

      nodes large update interval will lead to incorrect location information.

      0

      .

      ,

      (2)

      3 1 +2+ ( 2 2

      Numerical Values

      In this scheme, each neighbor record node i present position and velocity from the last beacon send by node i. Using a simple linear kinematic equation each of its

      The network coverage area is assumed to be a circle with a radius of 100 meters (i.e., x=100). The path loss exponent

      is assumed to be 2 . Quantities 1 and 2 + are assumed to be 6.6319 × 105 and 1.476 × 102 respectively. Nodal density varies from 0.005 to 0.08, which corresponds, on an average, a range of 157 to 2512 nodes in a circle with radius 100 meters.

   2. Adaptive Position Update

      Adaptive position update consists of two mutually exclusive rules. First one is the Mobility Prediction rule and the second one is the On-Demand Learning rule. Mobility prediction rule is used to reduce the beacon overhead and ODL is used to maintain an accurate local topology. Different postulations made in this method:

      • All nodes should know its location and velocity.

        neighbor periodically tracks nodes i `s location. Based on this position estimate, neighbors can check whether node i is still within their transmission range and update neighbor list accordingly. The goal of the MP rule is to send the next beacon update from node i when the error between the predicted location in the neighbors of i and node is actual location is greater than an acceptable threshold.

        In this scheme, to estimate nodes present position a simple location prediction scheme based on the physics of motion is used. In this thesis nodes are located in a 2D coordinate system with location indicated by x and y coordinates. The neighbors can estimate the current position of i, by using the following equations:

        = + (3)

      • All the connections should be bidirectional.

        1

        1

      • The beacon update includes the present position

        = + (4)

        of the node.

        1

        1

      • Data packets can piggyback location updates and all one-hop neighbor works in a promiscuous mode and hence the neighbors can overhear the data packets.

        In the first step, each node broadcast a beacon informing its neighbors regarding its existence and its present position and velocity. Following this, the earlier geographic routing protocol such as GPSR periodically broadcast its present position. Each node stores the position information from the neighboring node. Based on this position information each node incessantly updates its local topology, which is represented as a neighbor list. The possible candidates for packet forwarding can be chosen from this neighbor list. Thus, the beacon packet have significant role in upholding

        Note that, here and and and refers to the location and velocity information that was broadcast in the previous beacon from node i. Node i uses the same prediction scheme to keep track of its predicted location among its neighbors.

        1 1

        Acceptable Error Range

        If the deviation between the actual location and predicted location is greater than the threshold value, known as Acceptable Error Range, the node i will broadcast a new beacon (which includes the present position and velocity of node i).

        = ( )2 + ( )2 (5)

        an accurate local topology. The implementation of this method includes two mutually exclusive beacon triggering rules

      • Mobility Prediction

      • On-Demand Learning Rule

   Mobility Prediction Rule

   The MP rule adjusts the beacon generation rate to the frequency with which the nodes vary the characteristics that direct their motion (speed and direction). Beacon update by each node includes these motion characteristics. Using simple linear motion equation each node can locate the neighboring nodes motion. Nodes which dynamically changing their position need to frequently update its motion to the neighboring nodes. On the other hand, the slowly moving nodes need not send frequent update. At the same time a periodic beacon update strategy cannot assure both these requirements, since for slow nodes a small update interval will be wasteful, whereas for highly mobile

   Fig.2. Drawback of Mobility Prediction Rule

   Thus the MP rule tries to increase the effective duration of each beacon. The next beacon will be broadcasting only when predicted location information based on the last beacon becomes inaccurate. This maximize the beacon update interval for slow nodes, thus the number of beacon will be reduced. Additionally, highly mobile node can frequently broadcast beacon to ensure that their neighbors are aware of the quickly changing topology.

   On-Demand Learning Rule

   An accurate topology cannot be maintained by using the MP rule alone. Consider an example illustrated in fig.2., The node N is at position A1 it just sent a beacon. Since node M did not receive this beacon packet, it is unaware of the existence of N. Now, node N moves from A1 to A2 at a constant velocity. Assume that when node N moves from A1 to A2, the ARE is significantly large. So the MP rule is never triggered. From the figure b it can be appreciated that for significant portion of its motion node N is within the transmission range of M. The nodes N and M are unaware of each other. The situation is absolutely fine where neither N nor M are transmitting data. Now, if either N or M was transmitting data, they will eliminate each other on selecting the next hop node. So the local topology will not be updated for both nodes. In the worst case, the data packet would not be transmitted if no other nodes were in vicinity. Hence, it is indispensable to conceive a method to retain a more accurate local topology in the network where significant data forwarding are on-going. This is exactly what on-demand learning rule aims to achieve.

   Fig.3. Example of On-Demand Learning Rule

   Fig.4. Enriched Topology

   In this rulethe beacons will be broadcasted in response to the data forwarding activities that take place in the neighborhood of that node. According to this rule, beacons will be broadcasted as a reply whenever a node overhears a data transmission from new neighbor. The new neighbor means, the neighbor that was not in the neighboring list of this node. In veracity, to avoid collisions with other beacons a node waits for a small arbitrary time interval before responding with the beacon. Recollect that, data packets can piggyback location updates and all one-hop neighbor works in the promiscuous mode and hence can eavesdrop the data packets in their vicinity. In addition, since the data packet contains the location of the final destination, any node that overhears a data packet also checks its current location and determines if the destination is within its transmission range. If so, the destination node is added to the list of neighboring nodes, if it is not already present. Note that, this particular check incurs zero cost, that is, no beacons need to be transmitted.

   Fig.5. Comparison of Throughput

   Fig.6. Comparison of Packet Delivery Ratio

   In this work, during the initialization phase a neighboring list is maintained at each node and it uses the MP rule as the basic list. In response to the mobility of node and its neighbor the neighboring list is updated. The ODL rule allows active nodes that are involved in data forwarding to enrich their local topology beyond this basic set. In other words, the nodes keep up a rich neighboring list where in the regions having high traffic load. Thus, a rich neighboring list is maintained only at the active nodes and is built in response to the network traffic immediately. The basic lists in maintained in the nodes that are not take part in the data forwarding. Hence without acquiring additional delay ODL rule

   Fig.7. Comparison of Collision Rate

   Fig.8. Comparison of Normalized Routing Load

   guarantees alternate routes in situations where the nodes involved in the data forwarding are highly mobile.

   Fig.3, shows the network topology before node P starts sending data to node D. The red lines indicate that both P and D are aware of each other. P-Q-D is the first possible routing path from P to D. When P sends a data packet to Q, both R and S receive the data packet from P. According to ODL rule, both R and S will send back beacons to P because P is a new neighbor of R and S. Due to the effect of this, the link PR and PS will be discovered. Further, R and S identified that the destination D is within their one- hop neighborhood, based on their location and the location of destination. In the same way, when Q send the data packet to D, the link QR and QS will be discovered. Fig.4. shows the routing path from P to D along with the enriched topology.

   Note that, even if T and U receive the beacon from R and S, respectively, none of them respond back with a beacon. While T and U do not recline on the forwarding path, it is wasteful for them to send a beacon in response to the broadcast from R and S. In essence, for each traffic flow within the network the goal of ODL rule is to improve the accuracy of topology along the routing path from source to destination.

4. RESULT AND ANALYSIS

   The proposed protocol is implemented in NS-2. NS-2 version used is the NS-2.35-allinone. It has two output files, nam and trace file. The trace file is evaluated using AWK script. The trace file values are used to calculate the average packet delivery ratio, average throughput, average collision rate and normalized routing load. Different scenarios were taken for varying nodes (50300).

   Fig.5, shows the comparison graph of average throughput. The result shows that the proposed protocol, On-Demand Geographic Routing Protocol (OGRP) has greater throughput than GPSR. Throughput referred to as the maximum amount of data that can be transferred from one location to another in a given amount of time

   Fig.6, shows the comparison graph of average packet delivery ratio. It can be analyzed that, when comparing with the existing one, the proposed protocol achieves better packet delivery ratio. Packet delivery ratio is defined as the maximum number of packets that can be received by the destination from the total number of packets send by the source node.

   Fig.7, shows the graph of average collision rate. From the graph, it can be clear that the OGRP has lesser collision rate when compared with GPSR. Collision rate is defined as the rate at which the nodes collide with each other during packet transmission.

   Fig.8, shows the comparison graph of normalized routing load. It can be seen that GPSR has routing load greater than OGRP. Normalized routing load can be referred as the total time taken to send packets from source to destination.

5. CONCLUSION AND FUTURE WORK

   In this paper, The APU scheme employs two mutually exclusive rules. The MP rule uses mobility prediction to estimate the accuracy of the location estimate and adapts the beacon update interval accordingly, instead of using periodic beaconing. The ODL rule allows nodes along the data forwarding path to maintain an accurate view of the local topology by exchanging beacons in response to data packets that are overheard from new neighbors. From this work it can be found that the optimum transmission range can increase the performance. In this project the analytical model is validated with the simulation results. Also APU and optimum transmission range are embedded with OGPR. The proposed protocol results indicate that it generates better packet delivery ratio and throughput than the GPSR routing protocol. When comparing with the GPSR, the proposed protocol has lesser collision rate and routing load. Future work includes evaluating the performance of the proposed scheme on TCP connections in Mobile Ad hoc Networks.

6. REFERENCES

1 Brad Karp and H. T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks'', Proc. ACM MobiCom, pp. 243-254, Aug.2000, August 2000.

2 M. Sanchez, P. Manzoni, and Z. J. Haas, Determination of critical transmission range in ad hoc networks', in Proc. Multiaccess Mobility Teletraffic Wireless Commun. 1999 Workshop, Oct., pp. 293304.

3 Marc Heissenbuttel, Torsten Braun, Optimizing Neighbor Table Accuracy of Position-Based Routing, Proceedings of the 10th International Conference on Conceptual Structures, 2002.

4 H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Trans. On Commun., vol. COM-32, no. 3, pp. 246257, March 1984.

5 L. Blazevic, S. Giordano, and J.-Y. LeBoudec, A Location Based Routing Method for Mobile Ad Hoc Networks, IEEE Trans.Mobile Computing, vol. 4, no. 2, pp. 97-110, Mar. 2005.

1. Y. Ko and N.H. Vaidya, Location-Aided Routing (LAR) in Mobile Ad Hoc Networks, ACM/Baltzer Wireless Networks, vol. 6, no. 4, pp. 307-321, Sept. 2002.

2. J. Li, J. Jannotti, D.S.J.D. Couto, D.R. Karger, and R. Morris, A Scalable Location Service for Geographic Ad Hoc Routing, Proc. ACM MobiCom, pp. 120-130, Aug. 2000.

3. Z.J. Haas and B. Liang, Ad Hoc Mobility Management with Uniform Quorum Systems, IEEE/ACM Trans. Networking, vol. 7,no. 2, pp. 228-240, Apr. 1999.

4. A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica,Geographic Routing without Location Information, Proc. ACMMobi Com, pp. 96-108, Sept. 2003.

5. S. Lee, B. Bhattacharjee, and S. Banerjee, Efficient GeographicRouting in Multihop Wireless Networks, Proc. ACM MobiHoc, pp. 230-241, May 2005.

6. Y. Kim, R. Govindan, B. Karp, and S. Shenker, Geographic Routing Made Practical, Proc. Second Conf. Symp. Networked Systems Design and Implementation, pp. 217-230, May 2005.

7. F. Kuhn, R. Wattenhofer, and A. Zollinger, Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing, Proc. ACM MobiHoc, pp. 267-78, June 2003.

8. M. Heissenbuttel, T. Braun, M. Walchli, and T. Bernoulli, Evaluating of the Limitations and Alternatives in Beaconing,

Ad Hoc Networks, vol. 5, no. 5, pp. 558-578, 2007.