A Cross Layer Optimized Routing Protocol for Link Stability in Vehicle to Vehicle Communication (VANET)

A Cross Layer Optimized Routing Protocol for Link Stability in Vehicle to Vehicle Communication (VANET)

Ashilkumar R. Patel

Master in information technology @PIET

Yask Patel

Master in Computer Science

Abstract

Cross-layer design allows information to be exchanged and shared across layer boundaries in order to enable efficient and robust protocols. There has been several research efforts that validated the importance of cross-layer design in vehicular networks. Composed of mobile vehicles connected by wireless links. While the solutions based on the traditional layered communication system architectures such as OSI model are readily applicable, they often fail to address the fundamental problems in ad hoc networks, such as dynamic changes in the network topology. Furthermore, many ITS applications impose QoS requirements, which are not met by existing ad hoc networking solutions. So we are making the link stability based routing (LSR) algorithm of cross- layer design that introduced as an alternative to pure layered design to develop communication protocols.

1. Introduction

   In recent years, the number of motorists has been increasing drastically due to rapid urbanization. Critical traffic problems such as accidents and traffic congestion require the development of new transportation systems. The Intelligent Transportation Systems (ITS) are the integration of telecommunication and information technologies into transportation systems to improve the safety and efficiency of transportation systems.

   The main target of ITS is safety-related applications such as an emergency warning system which provides warning messages to vehicles in the affected area. Other informative and traveler- oriented applications include the electronic traffic information, electronic toll collection, etc. VANETs support two types of communication: vehicleto- vehicle (V2V) and vehicle-to- infrastructure (V2I). While V2V deals with communication among vehicles themselves, V2I is

   concerned about transmitting information between a vehicle and the fixed infrastructure that is installed along the road. Such infrastructure may include gateways or base stations, and they provide services such as Internet access in VANETs. Vehicular networks share a number of similarities with MANETs in terms of self-organization, self- management, and low bandwidth. However unlike in MANETs, the network topology in vehicular networks is highly dynamic due to fast movement of vehicles and the topology is often constrained by the road structure.

   Furthermore, vehicles are likely to encounter a lot of obstacles such as traffic lights, buildings, or trees, resulting in poor channel quality and connectivity. Therefore, protocols developed for traditional MANETs fail to provide reliable, high throughput, and low latency performance in VANETs. Thus, there is a pressing need for effective protocols that take the specific characteristics of vehicular networks into account.

   A major setback in applying MANET protocols to VANETS is the ability to adapt to conditions such as frequent topological changes. This adaptability issue is primarily due to the fact that VANET protocols are designed based on the standard OSI model of layered network stack architecture.

   They follow a divide-and-conquer approach to facilitate the interoperability among different computer systems. Such an architecture offers simplicity and modularity where the functionality of one layer is completely transparent from other layers. However, such a strict-layered architecture is not flexible enough to adequately support the needs of wireless communication in highly dynamic vehicular networks. The wireless communication in VANETs is inherently error-prone, and suffers from issues like noise, path loss and interference as in MANETs. In addition, VANETs must deal with vehicle high mobility and frequent route disruptions. Effective handling of these issues require an information exchange among layers so that one can jointly optimize different layers to achieve better

   throughput and good transmission latency. For example, routing protocols can leverage the information obtained from physical and MAC layers such as noise and interference levels to discover stable and best possible routes to the destination.

2. Cross-layer optimization solutions

   Practically speaking, communication between the layers means making the parameters at one layer visible to the other layers at runtime. By contrast, under a strictly layered architecture, every layer manages its own parameters, and its variables are of no concern to other layers. This information can be exchanged using protocol headers or extra interlayer. A cooperation of multiple layers would usually lead to a promising solution however certain cautionary should be taken into account when designing a cross-layer protocol to avoid a spaghetti design. Coverage, mobility support, delay and throughput differ significantly between these network architectures, and there is no single system that currently stands out as a single best solution to mobile sensor nodes.

   The suitability of the model according to the interaction between the layers is one important factor. Different crosslayer architectures are defined in [3]; i.e., direct communication between layers, a shared database across the layers, or a completely new abstraction. In the direct communication between layer models the information flow from one layer will be send upward, downward or back- and-forth as shown in Figure 1a.

   The shared database is like a new layer, providing the service of storage/retrieval of information to all the layers. Similarly, new interfaces between the layers can also be realized through the shared database as shown in Figure 1b. The main challenge here is the design of the interactions between the different layers and the shared database. We will refer to this database as the management subsystem in our discussion which is a method for this information to be exchanged between the connectivity subsystem and management subsystem. The third set of proposals present completely new abstractions, as depicted Figure 1c. Such novel organizations of protocols are appealing as they allow a great flexibility and rich interactions between the building blocks of the protocols. However, they may require completely new system- level implementations.

   Input variables: Some of the information that can be retrieved from different layers to apply for cross- layer optimisation are: Application layer: traffic model; Network layer: Queue length, route

   flow,traffic bandwidth, route hops, location, mobility path and topology information (i.e. the list of neighbours); Link layer Link state (link throughput, active schedules, rate, quality), radio duty cycle; Physical layer: power transmission, SNR, BER and sensor duty cycle. These input variables are applied for optimisation of variables across the layers, e.g., in transport layer session rate and packet reliability, in network layer route cost and route flows, in data link layer period of hello messages, link schedulers and timers and in physical layer transmitted power, rate and frequency.

3. Link Metrics

   We consider the changes in the link status mainly due to random mobility of the sensor nodes in a VANET. Initially the focus of this paper is exploiting the mobility information to improve the network data delivery reliability by using the mobility information in both MAC and network layer. The impact of mobility in VANET is on the status on links, such as link duration, link changes, link quality and stability. In this section we discuss the state of link can be measured. The accuracy of information depends on the measurement techniques applied; either active or passive. Active sampling adds more complexity and signalling to probe the state of the links real time but provides more accurate information compared to passive approach. The accuracy of passive monitoring mostly relies on the size of the monitoring window. To mai ntain the scalability of the algorithm we consider the passive monitoring of the state of the link in our design. In link/MAC layer link reliability can be monitored through forward error correction (FEC) and Automatic Repeat reQuest (ARQ); medium access protocol to avoid/reduce collisions; framing (with a particular frame-size) of data to be transmitted to ensure reliable transmission with minimal overhead. FEC/ARQ are related since both are used to improve link reliability. FEC requires transmission of extra bits to enable the receiver to recover the correct data in spite of bit-errors. ARQ on the other hand ensures reliability by retransmitting the corrupted frames i.e. the frames for which the receiver does not send an acknowledgment. Number

   of ARQ acknowledgements can show the level of reliability of the links. Another method to estimate the mobility based on actual mobility status of nodes is introduced by Vehicle Sensor MAC (VS-MAC). Each node discovers the presence of mobility within its neighbourhood based on the received signal levels of periodical synchronisation (SYNC) messages from its neighbours. Signal strength changes monitored continually at the link layer. If there is a change in a signal received from a neighbour, it presumes that it is relatively mobile to the neighbour. The level of change in the received signals also predicts the level of the mobiles speed. Instead of storing only information on the schedule of the sender node as for SMAC, the SYNC message in VS-MAC also includes information on the estimated speed of its mobile neighbour or mobility information. Therefore the relative speed ( v(i, j, t) ) between node (i,,j) can be measured by SYNC message in MAC layer. Meanwhile by monitoring the time

4. System Architecture And Protocol Design

   In this section, we present the architecture and design of the LSR protocol. We first give an overview of the network organization, and then describe the key LSR components in detail. Lastly, we present an analysis that derives the key performance metrics for the proposed protocol.

   1. Link Stability based routing

      As we discussed earlier, many of existing VANET routing protocols employ flooding of query messages in order to obtain a feasible path for the collected data from sensor nodes to be transferred to the sink nodes. Flooding of query messages results in a significant amount of redundancy, wastage of bandwidth, increase in number of collisions, and broadcast storm when many queries need to be flooded to the network. On one side of story, the unnecessary retransmission of flooding messages may guarantee that the information is forwarded to the entire network but the redundancy of the retransmission will raise the scalability issue. The number of retransmission increases as the density of the node increases. It should be noted that connectivity is not an issue in dense networks and therefore the idea of limiting the forwarding neighbours to reduce the flooding overhead will not affect on the connectivity of the network. On the other side of story, in a mobile scenario, routes often changes. The maintenance and update of these

      routes are costly and increases the delay in transmission. If the network has frequent link changes the information of some of the routes can become invalid after the route is set up. One way to reduce the overhead of routing is to set up long term routes by measuring the state of the links that floods the routing messages. With the proposed scheme, actually the link with the best quality is used. Such a strategy makes our scheme robust to link dynamics. An improved flooding mechanism minimizes the number of retransmissions for high density wireless sensor networks with frequent link changes which will be described in this section.

   2. The Protocol Design

      We propose link stability based routing (LSR) algorithm which aims to reduce the amount of flooding overhead to achieve better scalability and also select a more stable path to route the sensor node information to the sink node. This technique allows flooding protocol to select neighbours based on the information available at the link layer. For instance in Directed Diffusion algorithm, initial flooding is set artificially to a low data rate to avoid excess traffic. This solution can be enhanced by flooding the interest only to the more stable links as described below. We consider a dense network for two main reasons. Firstly since the flooding overhead is a significant scalability factor in dense networks. Secondly in dense environment eliminating unstable links to forward the data will not affect on the connectivity of the system. Every node should keep the information of its one-hop neighbourhood. It retransmits the flooding messages based on the neighbour policy management decision and disables the nodes to retransmit the message when they cannot meet certain level of link stability. When the link that a flooding message is forwarded is measured to be lower than an acceptable threshold then the node will not retransmit the flooding message to its neighbours. The idea of this protocol is not to cover more uncovered nodes but to retransmit to the stable areas which can ultimately results in more stable routing tables to reach a higher data delivery ratio. This design insures a higher reliability of the routes that are set up during the retransmission of the query messages, but on the other hand may result in network disconnectivity in a network that is not dense. Node 11 and 7 in Figure 3 are two examples of such scenario. Therefore the goal of this protocol is not to guaranty or to improve the number of covered nodes but aims to design a reliable delivery for mobile scenarios by excluding the unreliable and unstable routes.

   3. Cross-layer optimization

      Here we discuss that the method for selection of the next forwarding neighbor can be improved by taking link layer information for selecting next forwarding neighbours. The interaction of the information between link layer and network layer in connectivity subsystem and the shared information repository in the management subsystem according to the e_sense architectural model is illustrated in Figure 2. Consider a large scale, dense wireless sensor network, within which a source node generates reports on detected events. These reports will be delivered to the sink node via multi-hop routing.

      The selection based on the stability of the link is applied in this proposal which will lead to more stable route set up. Link When the flooding messages are broadcasted into the network, they create their reverse routing table to the query originator (sink node). To limit the nuber of flooding overhead, this protocol exploits a list of stable neighbours. This list should be maintained according to the status of the links to the immediate neighbours. A method to estimate the stability of the links is described in 3. As discussed already in neighbour table management policy section, maximum number of neighbours with a stable link

      (K) can be set according to the memory resources. Beside the resource improvement effect, when the network is static and links are equally stable, this mechanism will work similar to plain flooding if value K is not set. More discussion on the size of the neighbor table is presented in Subsection E.

      When a sensor node receives a query message, it configures its cache toward the source, and updates it if it receives the same query message from a different neighbour. It checks the sequence number of the two flooded messages and registers the next stable neighbour that provies the shortest path.

      This feature will optimise the energy efficiency of the protocol.

      With the help of the link stability measurement from link layer information the links are classified as stable or unstable. Figure 3 shows a network example with stable and unstable link status at time t that filters the query messages based on the status of the network links. The weights that should be considered when labelling a link as stable or unstable are the distance, mobility and connectivity weights. Distance weight measures by the received power of last few packets (e.g. flooding messages) using an appropriate channel propagation model. The connectivity weight is based on the duration of the two links to be on and the mobility reflects the effect of link changes during a monitoring time. Mobility can be retrieved from the speed of nodes as proposed in MS

      MAC. A sum of the three weights present the link stability weight assigned in the SNL

      of each node. Due to the nature of broadcasting, the query messages will be received by all the neighbours regardless of having a stable or an unstable link to the sender. On reception of the flooding messages from the unstable links, this message will be drop.

   4. Neighbour table

      A neighbour table stored the information needed for this selection. The idea is to maintain link layer information in this table of each of the SNs which

      can be exposed to network layer protocols. For instance link quality and scheduling can be used for routing decisions. A neighbour management policy can be applied to process and prepare the list of neighbours that should be kept in the neighbour list. The neighbour management maintains an effective summary of useful immediate neighbours which can be achieved by the neighbour table data structure. For the case of LSR, neighbour management maintains the information about link quality and power scheduling.

      The insertion and deletion of entries in the neighbour table are deferred to neighbour management to decide which entries belong to the table. An entry in the neighbour table usually consists of the address of the neighbour, link quality, and scheduling information. For added flexibility, the table is extensiblenetwork services and link protocols may add columns to it, such as routing gradients (e.g. in DD algorithm) or coordinates. Residual energy of the nodes can also be applied in the stability of the link status for the routing decisions. Typically the set of candidate neighbours is much larger than the set of useful neighbours (e.g., neighbours which can provide a stable and reliable link) and too large to retain in the memory of most microcontrollers.

      Thus, neighbour table management is critical. Maximum number of neighbours should be set according to the resource management protocol for a specific type of nodes.

   5. Neighbour table management policy

      The neighbour table of a device shall contain information on every device within transmission range, up to some implementation-dependent limit.

      After the SN has joined a network; neighbour table is used to store relationship an link-state information about neighbouring nodes. A table entry shall be updated every time a node receives any frame from the corresponding neighbours. When a new link is reported by link layer, the neighbour management policy allows the new entry to be inserted if the size of the neighbour will not exceed its maximum size after the insertion. If the maximum size is already reached, the entry with the least stability factor in the list will be compared with the new entry. The old entry will be replaced if its link

      stability factor is lower compared to the newly detected link. This policy provides the efficient use of memory resources in the SNs. In mobile scenarios, sensors locations can be stored in the shared information repository. The link quality and power scheduling information can be used for routing decisions. A neighbour management policy can be applied to process and prepare the list of neighbours that should be kept in the neighbour list. The reconfigurable neighbour policy management maintains an effective summary of useful immediate neighbours which can be achieved by theneighbour table data structure. An example of the mobility support in management subsystem as well as its interaction of the information between link layer and network layer inconnectivity system and the shared information repository in the management subsystem is illustrated in Figure 2.

   6. Routing decision

   The link stability density can be used to evaluate the stability of a route between a sink node and a sensor node. For example, consider a route with l links and let be the random variables representing each of the links stability at the time when the route is formed, given that the links have already been in existence for seconds respectively. Let P be a random variable representing the route stability formed by the l links. If we assume that the link stability factors are independent, then the distribution F (t) P of P can be calculated as: where Lj (t) si is the cumulative distribution function of the link stability of link j in the route, whose upstream node is moving with velocity ji v . Lj (t) si can be evaluated by integrating the corresponding density which depends on the mobility model applied in the VANET. The analysis for random way point mobility model has been addressed. The route stability distribution can be used for selection of the most suitable set of routes.

5. Conclusion

In this paper we discussed by sharing the information of network and link layer, the need for each layer to maintain its own neighbour table, is eliminated. This in turn reduces the storage requirement and avoids redundant measurements to estimate the link quality which improves the resource management in the VANET. We also discussed that unreliable communication environments, traditional routing protocols may fail to deliver data timely since link/node failures can be found out only after trying multiple transmissions. To tackle this problem and increase the reliability of the routes we propose link stability based routing mechanism to find and set up more stable paths and control the query flooding overhead. The shared information collected from link layer and network layer can improve the scalability and reliability of the routing. For instance, a link stability information and scheduling time can be maintained in a neighbour management repository which can be applied for routing mechanisms. We present the method to capture the state of the links in a vehicular environment and show the probability of the route stability based on the mobility model applied in the network.

ACKNOWLEDGEMENT

This research has been conducted on mobility exploitation in Vehicular ad-hoc network in the framework of the IST project which is funded by the European Union.

1. W. Alasmary and W. Zhuang, Mobility impact in IEEE 802.11p infrastructureless vehicular networks, Ad Hoc Networks, vol. 10, no. 2, pp. 222230, Mar. 2012.

2. S. Antipolis, Performance Comparison of AODV and OLSR in VANETs Urban Environments under Realistic Mobility Patterns, no. i.

3. M. Asefi, Quality-Driven Cross-Layer Protocols for Video Streaming over Vehicular Ad-Hoc Networks, 2011.

4. R. Baldessari, A. Festag, and J. Abeill, NEMO meets VANET: A Deployability Analysis of Network Mobility in Vehicular Communication, no. June, pp. 375380, 2007.

5. T. Chen, O. Mehani, and R. Boreli, Trusted routing for VANET, 2009 9th International Conference on Intelligent Transport Systems Telecommunications, (ITST), pp. 647652, Oct. 2009.

6. R. De and C. Des, C O M M U N I C AT I O N S, pp. 7488, 2008.

7. Z. Ding and K. K. Leung, Cross-Layer Routing Using Cooperative Transmission in Vehicular Ad-hoc

   Networks, IEEE Journal on Selected Areas in Communications, vol. 29, no. 3, pp. 571581, Mar. 2011.

8. F. J. Estrada and A. D. Jepson, Benchmarking Image Segmentation Algorithms, International Journal of Computer Vision, vol. 85, no. 2, pp. 167181, May 2009.

9. K. Z. Ghafoor, K. Abu Bakar, K. Lee, and H. AL-Hashimi, A Novel Delay- and Reliability- Aware Inter-Vehicle Routing Protocol, Network Protocols and Algorithms, vol. 2, no. 2, pp. 6688, Jun. 2010.

10. M. Ghassemian and H. Aghvami, A cross-layer optimisation solution to improve routing protocol performance for dense wireless sensor environment, 2007 3rd International Conference on Intelligent Sensors, Sensor Networks and Information, pp. 4348, 2007.

11. B. Jarupan and E. Ekici, A survey of cross-

    layer design for VANETs, Ad Hoc Networks, vol. 9, no. 5, pp. 966983, Jul. 2011.

12. K. Katsaros, M. Dianati, and K. Roscher, A Position-based Routing Module for Simulation of VANETs in NS-3, Proceedings of the Fifth International Conference on Simulation Tools and Techniques, 2012.

13. T. Kaur and A. K. Verma, Simulation and Analysis of AODV routing protocol in VANETs, no. 3, pp. 293301, 2012.

14. S. Khan, Y. Peng, E. Steinbach, M. Sgroi, W. Kellerer, D. Communications, and L. Europe,

    Optimization for Video Streaming over Wireless Networks, no. January, pp. 122130, 2006.

15. B. Paul, M. Ibrahim, and M. Abu Naser Bikas,

    VANET Routing Protocols: Pros and Cons, International Journal of Computer Applications, vol. 20, no. 3, pp. 2834, Apr. 2011.

16. T. V. L. N. Sivakumar and K. Sezaki, Cross- layer optimized routing for Bluetooth personal area

    network, Proceedings. 13th International Conference on Computer Communications and Networks (IEEE Cat.

    No.04EX969), pp. 155160.

17. P. Tomar, B. K. Chaurasia, and G. S. Tomar,

    State of the Art of Data Dissemination in VANETs, vol. 2, no. 6, pp. 957962, 2010.

18. L. Zhou, B. Zheng, B. Geller, A. Wei, S. Xu, and Y. Li, Cross-layer rate control, medium access control and routing design in cooperative VANET, Computer Communications, vol. 31, no. 12, pp. 2870 2882, Jul. 2008.

19. LEARNING FOR CROSS-LAYER OPTIMIZATION Fangwen Fu , and Mihaela van der Schaar University of California Los Angeles ( UCLA ) { fwfu , mihaela }@ ee . ucla . edu, pp. 6974.

20. Y. S. Ý, Y. T. H. Ý, H. D. S. Þ, and S. F. M. Ý,

    Cross-Layer Optimization for Routing Data Traffic in UWB-based Sensor Networks, 2005.

21. Y. Zhang and L. Cheng, Cross-Layer Optimization for Sensor Networks, pp. 1113.

22. S. Shabdanov, P. Mitran, and C. Rosenberg,

    Cross-Layer Optimization Using Advanced Physical Layer Techniques in Wireless Mesh Networks, IEEE Transactions on Wireless Communications, vol. 11, no. 4, pp. 16221631, Apr. 2012.

23. M. Luis, R. Oliveira, L. Bernardo, and P. Pinto,

    Improving routing performance in high mobility and high density ad hoc vehicular networks, 2010 IEEE Sarnoff Symposium, no. 1, pp. 16, Apr. 2010.

24. R. Toledo-Moreo and M. a. Zamora-Izquierdo,

    IMM-Based Lane-Change Prediction in Highways With Low-Cost GPS/INS, IEEE Transactions on Intelligent Transportation Systems, vol. 10, no. 1, pp. 180185, Mar.

    2009.

25. G. Song, S. Member, Y. G. Li, and S. Member,

    Cross-Layer Optimization for OFDM Wireless Networks

    Part I: Theoretical Framework, vol. 4, no. 2, pp. 614624, 2005.

26. S. Mohammad, M. Feiz, A. Movaghar, and K. Island, Comparison of DSR , AODV and DSDV Routing Protocols in Fully and Partially Connected VANET.

27. B. Mustafa, Issues of Routing in VANET, 2010.

28. G. D. Delgado, V. C. Frías, and M. A. Igartua,

    Cross-Layer Optimization for Video-streaming Transmission with QoS over Ad Hoc Networks: A Holistic Approach, pp. 13, 2007.

29. R. Singla, S. Sharma, and G. Singh,

    Performance Evaluation Of Routing Protocols In Vanets By Using Tcp Variants On Omnet ++ Simulator, vol. 2, no. 5, pp. 17251731, 2012.

30. R. Singla, S. Sharma, and G. Singh,

    Performance Evaluation Of Routing Protocols In Vanets By Using Tcp Variants On Omnet ++ Simulator, vol. 2, no. 5, pp. 17251731, 2012.

31. K. Katsaros, M. Dianati, R. Tafazolli, and R. Kernchen, CLWPR A novel cross-layer optimized position based routing protocol for VANETs, 2011 IEEE Vehicular Networking Conference (VNC), pp. 139146, Nov. 2011.

32. A. Wireless, M. Sensor, and N. Wmsns, Cross- Layer QoS-Aware Communication for Ultra Wide Band Wireless Multimedia Sensor Networks, vol. 28, no. 5, pp. 653663, 2010.

33. K. Zhu, D. Niyato, P. Wang, E. Hossain, and D.

    I. Kim, Mobility and Handoff Management in Vehicular Networks: A Survey, vol. 20, pp. 120, 2009.

34. A. Takano, H. Okada, and K. Mase,

    Performance Comparison of a Position-Based Routing Protocol for VANET, 2007 IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems, pp. 1 6, Oct. 2007.

35. S. Methodologies, Cross Layer Optimization: System Design and Simulation Methodologies, no. November, 2003.

36. U. Nagaraj, M. U. Kharat, and P. Dhamal,

Study of Various Routing Protocols in VANET, vol. 8491, no. iii, pp. 4552, 2011.