ISSN: 2229-371X

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

A DYNAMIC POSITION BASED ROUTING PROTOCOL TO OPTIMIZE PACKET DELIVERY IN MOBILE ADHOC NETWORK

Saranya. S1, Chandrasekaran.R2
  1. PG Student, Computer Science and Engineering, Bharath Institute of Science and Technology, Chennai, India
  2. Asst.Prof, Computer Science and Engineering, Bharath Institute of Science and Technology, Chennai, India
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

Mobile Ad hoc networks (MANET) carried out multi-hop communication in an environment with no fixed infrastructure, by means of mobile nodes and changing network topology. In the earlier period, hundreds of new routing protocols were designed for the various scenarios of MANET. Most existing ad hoc routing protocols are liable to node mobility, especially for large-scale networks. Provoked by this issue, this paper presents the new approach a Dynamic Position Based Routing (DPBR) protocol which implemented in the distributed architecture and takes advantage of the stateless property of geographic routing and the broadcast nature of wireless medium dynamically. When a data packet is sent out, some of the neighbor nodes that have eavesdropped with the transmission will serve as forwarding candidates, and take turn to forward the packet if it is not in a position to receive. By utilizing such uphill backup, this paper concentrate on how the new examine model supports to reduce the packet drop as well as increase delivery ratio dynamically. The additional latency earn by local route recovery is greatly reduced and the duplicate relaying caused by packet reroute is also decreased. Both theoretical analysis and simulation results show that DPOR achieves excellent performance even under high node mobility with acceptable overhead.

Keywords

Distributed architecture, High packet delivery, Geographical Routing;

INTRODUCTION

MOBILE ad hoc networks (MANETs) have gained a great deal of attention because of its significant advantages carried about by multihop, infrastructure-less transmission. On the other hand, due to the error prone wireless channel and the dynamic network topology, reliable data delivery in MANETs, especially in challenged environments with high mobility residue an issue. MANET is used to communicate between hosts in the absence of dedicated routing infrastructure, when messages are forwarded by intermediate hosts if the sender and receiver are out of communication range. The quality of such a routing algorithm can be measured by its delivery ratio that be supposed to maximum; that is, the ratio of the number of data packets received at the destination to the number of data packets sent by the source. Traditional topology-based MANET routing protocols (e.g., DSDV, AODV, DSR [1]) are relatively liable to node mobility. The main cause is due to the end-to-end route discovery is before data transmission. Owing to the constantly and even fast changing network topology, it is very difficult to maintain a deterministic route. The discovery and recovery procedures are also time and energy consuming. Once the path shatters, data packets will get lost or be delayed for a long time in anticipation of the renewal of the route, causing transmission disruption.
Geographic ad-hoc networks, using position-based routing, are targeted to handle large networks containing many nodes. Such networks are inappropriate to use topology based algorithm as the amount of resources required would be vast. The advantage in geographic networks is the ability to deliver a packet from its source to the destination based as much as possible on local information without keeping network-wide information [2]. While topology based algorithms may be more efficient in delivering packets in terms of delivery success probability and route optimality, position based routing has the advantage of modest memory requirement at the node and low control message overhead, which also translate to more efficient use of power resources [3]. While this is not a full comparison between the two groups, it emphasizes the will to center position-based routing algorithms as much as possible on local information. Actually, due to the broadcast nature of the wireless medium, a single packet transmission will lead to multiple receptions. If such transmission is used as backup, the strength of the routing protocol can be significantly enhanced. The concept of such multicast-like routing strategy has already been demonstrated in opportunistic routing [4]. Conversely, most of them use link-state style topology database to select and prioritize the forwarding candidates.
In this paper, a Dynamic Position-Based Routing (DPBR) protocol is proposed, and implemented in distributed architecture, in which several forwarding candidates cache the packet that has been received using MAC interception. If the best forwarder does not forward the packet in certain time slots, suboptimal candidates will take turn to forward the packet according to a locally formed order. In this way, providing one of the candidates succeeds in receiving and forwarding the packet, the data transmission will not be interrupted. Potential multipaths are broken on the soar on a per packet DPBR’s excellent strength can be projected. The paper is structured as follows: Section 2 discusses related work. Section 3 presents our proposed service model and stipulating architecture. Section 4 converses the implementation of DPBR protocol. Section 5 discusses simulation results that show the efficiency of our approach compared with AOMDV and GPSR. Finally, Section 5 concludes this work.

RELATED WORK

In so far as, there are no geographic routing protocols that are adaptive to the demand of traffic transmissions. The conventional on-demand routing protocols [5],[6] often involve flooding in route discovery phase, which limits their scalability. Unlike topology-based routing protocols, geographic routing protocols [7] are based on mobile nodes positions. Some current geographic routing studies focus on the improvement and design of forwarding schemes [8], designing routing metric [9] or analyzing the routing performance [10]. Tschopp et al. [11] have tried to combine geographic routing and topology-based routing in ad-hoc networks to overcome the shortcomings of both kinds of routing. The work uses a beacon based algorithm for the embedding of the connectivity graph. However, the inevitable twist of the embedding will result in non-optimal routing and even forwarding failure.
The position information has the following three sources which all impact routing performance, with the first two assumed to be known and the third one contained in geographic routing protocols: 1) positioning system (e.g., GPS): each node can be aware of its own position through a positioning system, which may have measurement inaccuracy. 2) Location service: every node reports its position periodically to location servers located on one or a set of nodes. The destination positions obtained through these servers are based on node position reports from the previous cycle and may be outdated. 3) Local position distribution mechanism: every node periodically distributes its position to its neighbors so that a node can get knowledge of the local topology. Recently the impact of the position inaccuracy from the first source has been studied in [12],[13] and the second one is discussed in [14]. Being an important self-contained part of geographic routing protocols, the design of position distribution method will affect local topology knowledge and therefore geographic forwarding, but little work has been done to study and avoid its negative impact. Son et al. [14] carried out a simulation based study on the negative effect of mobility-induced location error on routing performance. Our routing schemes are designed to be efficient and robust, with adaptive parameter settings, flexible position distributions and route optimization. Authors in [15], [16] and [17] attempted to remove the proactive beacons in geographic routing protocols to reduce overhead. CBF [17] and GeRaF [15] proposed different schemes to avoid argument in selecting the next-hop forwarding nodes.
The need of changes at both the MAC layer and the network layer increases the complexity of the two protocols and the uncertainty of the performance. In [18], an opportunistic retransmission protocol PRO is proposed to manage with the undependable wireless channel. Implemented at the link layer, PRO leverages on the path loss information Receiver Signal Strength Indicator (RSSI) to select and prioritize relay nodes. By assigning the higher priority relay a smaller disputation window size, the node that has higher packet delivery ratio to the destination will be preferred in relaying. With respect to the impact of mobility, Wu et al. [19] investigate the WiFi connectivity for moving vehicles, with focus on the cooperation among BSs. BSs that overhear a packet but not its acknowledgment probabilistically relay the packet to the intended next hop. In our work we extend the opportunistic forwarding with the distributed environment where the core and access router supports for dynamic implementation.

SERVICE MODEL AND DYNAMIC POSITION BASED ROUTING

The design of DPBR is based on the opportunistic forwarding and executed in the service model that composed by core and access routers, as shown in Fig. 1.
image
The Access routers are to be aware of their own location and the positions of neighboring nodes. Neighborhood location information can be exchanged using one-hop beacon or piggyback in the data packet’s header. Core routers send messages with access routers to report the congestion situation. When a source node wants to transmit a packet, it gets the location of the destination first and then attaches it to the packet header. Due to the destination node’s movement, the multihop path may diverge from the true location of the final destination and a packet would be dropped even if it has already been delivered into the neighborhood of the destination. To deal with such issue, additional check for the destination node is introduced. At each access router, it will check its neighbor list to see whether the destination is within its transmission range. If yes, the packet will be directly forwarded to the destination, similar to the destination location prediction scheme described in [4]. The forwarding table is constructed dynamically during data packet transmissions and its preservation is much easier than a routing table. As the establishment of the forwarding table only depends on local information, it takes much less time to be constructed. The table records only the current active flows, while in conventional protocols, a decrease in the route expire time would require far more resources to rebuild. Algorithm 1 depicts the procedure to select and prioritize the forwarder list.
image
The lower the index of the node in the candidate list, the higher priority it has.As the data packets are transmitted in a multicast-like form, each of them is identified with a unique tuple (src_ip,seq_no) where src_ip is the IP address of the source node and seq_no is the corresponding sequence number. Each access router maintains a monotonically increasing sequence number, and an ID_Cache to record the ID (src_ip, seq_no) of the packets that have been recently received. If a packet with the same ID is received again, it will be discarded. Otherwise, it will be forwarded at once if the receiver is the next hop, or cached in a Packet List if it is received by a forwarding candidate, or dropped if the receiver is not specified.

SIMULATION RESULTS

In order to evaluate the performance of the proposed protocol, run simulations using the NS-2 network simulator, version 2.33. During a simulation, the initial data rate depends on the channel position recommended by receiver. The information from the sender is sent with equal size of packets (512 bytes). The algorithm for congestion control is implemented in the core router to identify the congestion. The core router receives the message in this regard and intimate to the nodes involved in the transmission. Core router also monitors the channel misbehaviors and intimate to sender. The proposed routing protocol DPBR is implemented in the access router to update the forwarding table. The access router dynamically assists to choose the forwarder to avoid superfluous dropping of packets. The parameters used for the simulation scenario is presented on Table.1
image
This section presents the comparison between the accuracy of proposed routing algorithm with AOMDV [20] (a famous multipath routing protocol) and GPSR [21] (a representative geographic routing protocol). In our scenario we measure the effectiveness of the proposed routing algorithm with the network that consists of 2 core nodes, 6 access nodes, 40 end nodes (20 source-destination pairs). The buffer size of each link can contain 50 packets. Fig.2 depicts the performance of proposed routing algorithm in the metric throughput. Throughput is the number of useful bits per unit of time forwarded by the network from a certain source to a certain destination.
image
The performance metric packet delivery ratio defines that the ratio of the number of data packets received at the destination to the number of data packets sent by the source is illustrated in the fig.3.
image
The Fig. 4 corresponds to End to End Delay, which is defined as the average time taken by the packet to reach the destination node from the source node. Delay = (total_packets_sent) / (simulation_time)
The result clearly shows that the performances of all the approaches are almost equal when the simulation starts. But it performs better than the other approaches when the time increases.
image
The fig. 5 shows the packet drop that is the number of packets dropped due to the effect of mobility of nodes. The dropped packets may be a control packets or data packets. The proposed algorithm is optimized in the packet drop because of the reason that the proposed algorithm centered on dynamic updating on forwarding table.
image

CONCLUSION

In this paper, we address the problem of reliable data delivery in highly dynamic mobile ad hoc networks. Continually changing network topology makes conservative ad hoc routing protocols incapable of providing satisfactory performance. In spite of frequent link break due to node mobility, substantial data packets would either go astray. Stimulated by opportunistic routing, we propose a MANET routing protocol DPBR which takes advantage of the stateless property of geographic routing and broadcast nature of wireless medium. In addition selecting the next hop, several forwarding candidates are also explicitly specified in case of link break. Leveraging on such natural backup in the air, broken route can be recovered in a timely manner. The efficacy of the involvement of forwarding candidates against node mobility is analyzed. Through simulation, the effectiveness and efficiency of proposed routing method has confirmed. In addition, the metric high packet delivery ratio is achieved while the delay and duplication are the lowest.

References

  1. Ahmed Al-Maashri and Mohamed Ould-Khaoua. ―Performance Analysis of MANET Routing Protocols in the Presence of Self-Similar Traffic‖. IEEE, ISSN- 0742-1303, First published in Proc. of the 31st IEEE Conference on Local Computer Networks, 2006.
  2. Y. Kim, J.-J. Lee, and A. Helmy, ―Modeling and Analyzing the Impact of Location Inconsistencies on Geographic Routing in Wireless Networks,‖ Mobile Computing and Comm. Rev., vol. 8, no. 1, pp. 48-60, 2004.
  3. I. Stojmenovic, ―Position based routing in ad hoc networks,‖ IEEE Commun. Mag., vol. 40, no. 7, pp. 128–134, 2002.
  4. S. Biswas and R. Morris, ―EXOR: Opportunistic Multi-Hop Routing for Wireless Networks,‖ Proc. ACM SIGCOMM, pp. 133-144, 2005.
  5. M.K. Marina and S.R. Das, Performance of routing caching strategies in dynamic source routing, in: 2001 International Conference on Distributed Computing Systems Workshop (2001).
  6. Y.-C. Hu and D.B. Johnson, Caching strategies in on-demand routing protocols for wireless ad hoc networks, in: The 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom) (August 2000).
  7. H. Frey. ―Scalable Geographic Routing Algorithms for Wireless Ad Hoc Networks.‖ IEEE Network, Vol. 18, Jul./Aug. 2004, pp. 18-22.
  8. J. Li and et al, ―A scalable location service for geographic ad hoc routing,‖ in ACM/IEEE MOBICOM, 2000, pp. 120–130.
  9. F. Zhang, H. Li, A. Jiang, J. Chen, and P. Luo, ―Face Tracing Based Geographic Routing in Nonplanar Wireless Networks,‖ Proc. IEEE INFOCOM, pp. 2243-2251, May 2007.
  10. J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. G. Jetcheva, ―A performance comparison of multihop wireless ad hoc network routing protocols,‖ in ACM/IEEE MOBICOM, 1998, pp. 85–97.
  11. D. Tschopp, S. Diggavi, M. Grossglauser, and J. Widmer, ―Robust Geo-Routing on Embeddings of Dynamic Wireless Networks,‖ Proc. IEEE INFOCOM, May. 2007.
  12. K. Seada, A. Helmy, and R. Govindan, ―On The Effect of Localization Errors on Geographic Face Routing on Sensor Networks,‖ Proc. IEEE Third Int’l Workshop Information Processing in Sensor Networks (IPSN), 2004.
  13. Y. Kim, R. Govindan, B. Karp, and S. Shenker, ―Lazy Cross-Link Removal for Geographic Routing,‖ Proc. Fourth Int’l Conf. Embedded Networked Sensor Systems (Sensys), 2006.
  14. D. Son, A. Helmy, and B. Krishnamachari, ―The Effect of Mobility- Induced Location Errors on Geographic Routing in Ad Hoc Networks: Analysis and Improvement Using Mobility Prediction,‖ Proc. Wireless Comm. and Networking Conf. (WCNC ’04), 2004.
  15. M. Zorzi and R.R. Rao, ―Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance,‖IEEE Trans. Mobile Computing, vol. 2, no. 4, pp. 337-348, Oct.-Dec. 2003
  16. M. Heissenb, T. Braun, T. Bernoulli, and M. Wlchli, ―BLR: Beacon- Less Routing Algorithm for Mobile Ad-Hoc Networks,‖ Elsevier’s Computer Comm. J., vol. 27, no. 11, pp. 1076-1086, July 2003.
  17. H. Fussler, J. Widmer, M. Kasemann, M. Mauve, and H. Hartenstein, ―Beaconless Position-Based Routing for Mobile Ad- Hoc Networks,‖ Technical Report TR-03-001, Dept. of Math. and Computer Science, Univ. Mannheim, Germany, 2003.
  18. Mei-Hsuan Lu , Peter Steenkiste and Tsuhan Chen “Design, Implementation and Evaluation of an Efficient Opportunistic Retransmission Protocol‖, MobiCom ’09, September 20-25, 2009,Beijing, China
  19. F. Wu, T. Chen, S. Zhong, L.E. Li, and Y.R. Yang, ―Incentive-Compatible Opportunistic Routing for Wireless Networks,‖ Proc. ACM MobiCom, pp. 303-314, 2008.
  20. M. Marina and S. Das, ―On-Demand Multipath Distance Vector Routing in Ad Hoc Networks,‖ Proc. Ninth Int’l Conf. Network Protocols (ICNP ’01), pp. 14-23, Nov. 2001.
  21. B. Karp and H.T. Kung, ―GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,‖ Proc. ACM MobiCom, pp. 243-254, 2000