عنوان مقاله
الگوی مسیریابی قابل اعتماد مبتنی بر گراف در حال تکامل برای VANETها
فهرست مطالب
مقدمه
کارهای مرتبط
مدل قابلیت اعتماد وسایل نقلیه
مدل گراف در حال تکامل VANET گرا
پروتکل مسیریابی بردار فاصله برحسب تقاضای اقتضایی قابل اعتماد با گراف در حال تکامل
نتیجه گیری
بخشی از مقاله
رویکرد میکروسکوپی اعمالی مانند افزایش شتاب، کاهش شتاب، و تغییر خط هر وسیله نقلیه به ترافیک‌های پیرامون را مدل می‌کنند. این می‌داند که رویکرد ماکروسکوپی می‌تواند برای شرح وضعیت جریان ترافیکی خودروهای عمومی و شخصی استفاده شود. از این رو، از مدل جریان ترافیک ماکروسکوپی برای شرح جریان ترافیک وابسته به خودروهای نقلیه و استفاده از سرعت میانگین برای بررسی توزیع ریاضی حرکت وسایل نقلیه در طول شبکه گرافیکی استفاده می‌کنیم.
کلمات کلیدی:
An Evolving Graph-Based Reliable Routing Scheme for VANETs Mahmoud Hashem Eiza and Qiang Ni, Senior Member, IEEE Abstract—Vehicular ad hoc networks (VANETs) are a special form of wireless networks made by vehicles communicating among themselves on roads. The conventional routing protocols proposed for mobile ad hoc networks (MANETs) work poorly in VANETs. As communication links break more frequently in VANETs than in MANETs, the routing reliability of such highly dynamic networks needs to be paid special attention. To date, very little research has focused on the routing reliability of VANETs on highways. In this paper, we use the evolving graph theory to model the VANET communication graph on a highway. The extended evolving graph helps capture the evolving characteristics of the vehicular network topology and determines the reliable routes preemptively. This paper is the first to propose an evolving graph-based reliable routing scheme for VANETs to facilitate quality-of-service (QoS) support in the routing process. A new algorithm is developed to find the most reliable route in the VANET evolving graph from the source to the destination. We demonstrate, through the simulation results, that our proposed scheme significantly outperforms the related protocols in the literature. Index Terms—Evolving graph, quality of service (QoS), routing reliability, vehicular ad hoc network (VANET), vehicular networks. I. INTRODUCTION E VERY DAY, a lot of people die, and many more are injured in traffic accidents around the world. The desire to disseminate road safety information among vehicles to prevent accidents and improve road safety was the main motivation behind the development of vehicular ad hoc networks (VANETs). VANETs are a promising technology to enable communications among vehicles on roads [1]. They are a special form of mobile ad hoc networks (MANETs) that provide vehicle-tovehicle communications. It is assumed that each vehicle is equipped with a wireless communication facility to provide ad hoc network connectivity. VANETs tend to operate without an infrastructure; each vehicle in the network can send, receive, and relay messages to other vehicles in the network. This way, vehicles can exchange real-time information, and drivers can be informed about road traffic conditions and other travel-related information. VANETs have attractive and unique Manuscript received June 15, 2012; revised October 15, 2012 and January 16, 2013; accepted January 17, 2013. Date of publication February 1, 2013; date of current version May 8, 2013. The review of this paper was coordinated by Prof. M. Haenggi. M. H. Eiza is with the School of Engineering and Design, Brunel University, London UB8 3PH, U.K. (e-mail: Mahmoud.HashemEiza@brunel.ac.uk). Q. Ni is with the School of Computing and Communications, Lancaster University, Lancaster LA1 4WA, U.K. (e-mail: Q.Ni@lancaster.ac.uk). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TVT.2013.2244625 features, distinguishing them from other types of MANETs, such as normally higher transmission power, higher computational capability, and some kind of predictable mobility, in comparison with general MANETs [2]. The special behavior and characteristics of VANETs raise important technical challenges that should be considered to deploy these networks effectively. The most challenging issue is potentially the high mobility and the frequent changes of the network topology [3], [4]. In VANETs, the network topology could vary when the vehicles change their velocities and/or lanes. These changes depend on the drivers and road situations and are normally not scheduled in advance. The graph theory can be utilized to help understand the topological properties of a VANET, where the vehicles and their communication links can be modeled as vertices and edges in the graph, respectively. Recently, a graph theoretical model called evolving graph [5], [6] has been proposed to help capture the dynamic behavior of dynamic networks when mobility patterns are predictable. This model has shown its promising results in MANETs and delay-tolerant networks [7], [8]. However, the current evolving graph theory can be only applied when the topology dynamics at different time intervals can be predicted; these are known as fixed scheduled dynamic networks (FSDNs). VANETs cannot be treated as FSDNs, and hence, the existing evolving graph theory cannot be directly applied to VANETs. Fortunately, the pattern of topology dynamics of VANETs can be estimated using the underlying road networks and the available vehicular information. Hence, we can categorize this type of dynamic network as a predicted pattern dynamic network. Consequently, the current evolving graph theory could be extended to deal with VANETs. The objective of this paper is to propose a novel evolving graph-based reliable routing scheme for VANETs. The novelty of this work lies in its unique design of a reliable routing protocol that considers the topological properties of the VANET communication graph using the extended evolving graph. Considering that vehicles travel at high speeds on highways, the data delivery service could have many disruptions due to frequent link breakages. It is very important to ensure that the most reliable links are chosen when building a route. The major contributions of this paper are given here. 1) A new link reliability model based on the mathematical distribution of vehicular movements and velocities on the highway is developed. 2) The current evolving graph model is extended to capture the evolving features of the VANET communication graph, and the link reliability metric is considered.
