Link Lifetime based Border Node (LLBN) Protocol

Link Lifetime based Border Node (LLBN) Protocol Link Lifetime based Border Node (LLBN) Protocol for Vehicular Ad Hoc Networks Sanjay Batish, Manisha Chahal, Sanjeev Sofat, Amardeep Singh Abstract Vehicular ad hoc network (VANET) attracts rising attentions of researchers for safety related and other communication applications. These networks have many challenging characteristics such as high mobility, fast changing topology and limitation of bandwidth. Under these problems, we proposed LLBN (link lifetime based border node protocol). Keywords VANETs, Routing Protocol, Position based Routing, GPSR 1. Introduction Vehicular ad hoc networks (VANETs) is emerging as an immense technology in wireless network that enable communication among vehicles. This network consist of vehicles, computer controlled devices, road side infrastructures, radio transceivers and internet connection. It attracts significant researchers, industry and government towards road safety, traffic control management and entertainment applications. Due to limitation of bandwidth spectrum, United State Federal Communications Commission (FCC) allocated 75MHz of bandwidth spectrum in 5.9 GHz band. Vehicles can communicate at a data rate of 6-27 Mbps up to a range of 1000m. VANET is a part of mobile ad hoc networks (MANETs). Many of existing routing protocols for MANETs are not suitable for VANET. Position based (geographic or location based) routings protocols are most suitable for VANET environment due to extremely dynamic topology and repeatedly disconnected network. In these types of routing protocols, forwarding decision is based on location of destination and location of nodes one-hop neighbors called as position based greedy forwarding routing. Border node based protocols, for example Border-node based most forward with in radius (BMFR) follow greedy forwarding by considering concept of border node. Border node concept is used to reduce the hop count between sender node and destination node, that lead to conservation of bandwidth. Nodes lie on transmission range of a particular node are called as border node. This idea of border node suffer from link failure due to unrestricted road patterns and dynamic topology. In this paper, we proposed a link lifetime based border node protocol (LLBP) to perk up existing unicast location based routing protocols. If b-mfr results several border nodes projected at same point towards destination, then check for most stable path by considering link life span. 2. Related Work 2.1. Border Node Based Routing (BBR) Protocol M. Zhang and Richard S. Wolff have proposed BBR to minimize total no for nodes involved in routing process. Here, every node maintain three tables: Neighbor Table, Border Node Selection Table and the Forward Table. It works in two phase, first one is neighbor discovering like in all other position based protocols and next phase is border node selection process. 2.2. Greedy Perimeter Stateless Routing (GPSR) protocol B. Karp and H.T. Kung have discovered GPSR position based protocol for vehicular network. In greedy mode each node forwards packets to next hop that is constantly nearer to destination, until the packet reaches its final destination. GPSR recovers from a local maximum using perimeter mode. It uses an algorithm of planer graph traversal to find a way out of the local maximum region. 2.3. Border-node based most forward with in radius (BMFR) Ram Shringar Raw, D K Lobiyal have proposed this protocol by making use of border node. One-hop neighbor selection method is same as other position based protocols but here border node consider as a next-hop node for forwarding packet from source to destination. Under border node selection process, select the one which is maximum projected towards the destination. In this protocol, problem of confliction( as shown in figure 1) between two or more border nodes may occur. Figure 1. Problem in BMFR 2.4. Movement-Based Routing Algorithm (MORA) F. Granelli and G. Boato have applied this algorithm on GPSR. It considers approach of movements of vehicles along with the position of vehicles. Firstly sender node flooded the network with route request message . Destination node send route reply message with a specific metric. After that sender transmit data according to method used in GPSR protocol. 2.5. Movement Prediction-Based Routing (MOPR) Protocol H. Menouar and F. Filali proposed MOPR protocol to improve the MORA. This protocol also consider speed of vehicle along with direction and position of vehicle. Vehicle, which is expected to go out the communication range in a short period time will not be selected as a next hop for data forwarding if some better node is available. 3. Link Lifetime based Border Node Routing To increase the performance of BMFR protocol, we have applied link lifetime on BMFR. As already discussed, BMFR decrease number of hop counts through which data packets travel, but a problem arises when more than two border node towards destination projected at same point. We believe that considering only the bandwidth is not enough in unicast routing. The vehicle movement and link failure should be taken into account. A border node which goes outside the radio transceiver range should not be selected as a next hop. We propose our LLBN concept applied to BMFR ( as shown in Figure 2,3). . Figure 2. Link life time calculation Figure 3. LLBN Protocol 4. Proposed Algorithm Case a: Send packet to most projected border node towards destination Notations NS: source node ND: destination node NRf: recent forwarding node Set: recent forwarding node neighbors SetS: set of selected node NextN: selected next node Rmax: maximum communication range LC: link constancy LLT[p, q]: link(p, q) life time 1. NCf = NS 2. if ( ND lies within Rmax(NRf) ) then send data to ND else go to step 3 3. Compute Euclidian distance of all nodes in Set from NRf 4. for all Ai ∈Set, i = 1 to n if (distance of Ai from NRf == Rmax) then SetS = SetS ∠ª Ai else interior nodes 5. Calculate projection(P) of Ai on line joining NS and ND 6. Choose next neighbor node (Nnext) having highest projection if (Nnext == 1) then // only one maximum // projected node send data to Nnext else if (Nnext ≠¥ 1) then // two or more maximum // projected nodes go to step 7 Case b: Confliction between two or more border nodes occurs (Xp0, Yp0): initial position of node p in X and Y coordinates (Xq0, Yq0): initial position of node q in X and Y coordinates Vp: speed of p vehicle Vq: speed of q vehicle t0: initial time t1: time after movement of nodes t = t1 t0 Din = initial link distance Dmov = link distance after movement Λ = constant routing route validity time D2mov = ( ( Xp0 + VXpt) (Xq0 + VXqt) )2 + ( ( Yp0 + VYpt) (Yq0 + VYqt) )2 D2mov = P t2 + Q t + R P = VXp VXq Q = R = Solve P t2 + Q t + R R2max = 0 LC[p, q] = LLT[p, q] / Λ find link having maximum LC[p,q] Conclusion References [1] Hamid Menouar, Massimiliano Lenardi and Fethi Filali Movement Prediction-based Routing (MOPR) Concept for Position-based Routing in Vehicular Networks, IEEE 66th Vehicular Technology Conference, Baltimore, MD, October 2007. [2] F. Granelli, G. Boato, and D. Kliazovich, MORA: a Movement-Based Routing Algorithm for Vehicle Ad Hoc Networks, IEEE Workshop AutoNet, San Francisco, U.S.A., December 2006. [3] Brad Karp and H. T. Kung, â€Å"GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,† ACM 6th annual international conference on Mobile computing and networking International Conference on Mobile Computing and Networking, Boston, MA, August 2000. [4] Mingliu Zhang and Richard S. Wolff Border Node Based Routing Protocol for VANETs in Sparse and Rural Areas, IEEE GLOCOMW, November 2007. [5] Ram Shringar Raw, D K Lobiyal B-MFR Routing Protocol for Vehicular Ad hoc Networks International Conference on Networking and Information Technology 2010.