Performance improvement of clustered-based VANET routing protocol

Abuashour, Ahmad (2018). Performance improvement of clustered-based VANET routing protocol. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (1MB) | Prévisualisation
Prévisualisation	PDF Télécharger (897kB) | Prévisualisation

Résumé

Vehicular Ad-Hoc NETworks (VANETs) have received considerable attention in recent years, due to its unique characteristics, which are different from Mobile Ad-Hoc NETworks (MANETs), such as rapid topology change, frequent link failure, and high vehicle mobility. The high mobility in VANETs causes high topology changes and in turn leads to excessive control overhead messages and frequent link failures.

Traditionally, clustering techniques have been used as the main solution to reduce the control overhead messages in VANET, in which the network is divided into multiple clusters and selecting one of the Cluster Members (CMs) as a Cluster Head (CH). The selected CHs are responsible for coordinating the members of the cluster, and communication between clusters. The clustering techniques will significantly reduce the routing control overhead messages, that is because the clustering techniques restrict the communication between each CM and it’s CH instead of communication between all the vehicles in the VANET topology.

The most important characteristic for any clustering technique is to create a stable cluster with minimum clustered control overhead messages. In this thesis, we define four types of clustered control overhead messages, as follows: The control overhead messages generated due to clustering formation and maintenance, the control overhead messages due to forwarded from the CMs to the CH, the periodically broadcasted advertisement messages by the CH, and the control overhead messages broadcasted due the CH election process. Also, we assume all VANET networks are already preclustered. Therefore, the clustered control overhead messages generated by the clustering formation or maintenance are eliminated. Furthermore, the clustered control overhead messages generated by the CM and the CH, and due to CH election processes still produce high clustered control overhead messages.

In the first part, the problem of Clustered-Based Routing (CBR) protocol in VANET is relaying the received data to unstable CH. Most of the proposed CH election algorithms select the CH in the clustered VANET topology by considering many parameters, such as: mobility, location, and node Life-Time (LT). Most of the clustering techniques produce unstable clustered VANET topology, because they do not elect the stable CH. Therefore, the cluster that elects the suitable CH which does not change frequently is considered a stable cluster. Also, it improves the CBR protocol performance in terms of throughput and end-to-end delay. Therefore, we propose a Cluster-Based Life-Time Routing (CBLTR) protocol. The CBLTR protocol aims to increase the route stability and average throughput in a bidirectional segment scenario. The Cluster Heads (CHs) are selected based on maximum Life-Time (LT) among all vehicles that are located within each cluster. We propose also an Intersection Dynamic VANET Routing (IDVR)protocol. The IDVR protocol aims to increase the average throughput, and to reduce end-toend delay in a grid topology. The elected Intersection CH (ICH) receives a Set of Candidate Shortest Routes (SCSR) close to the desired destination from the Software Defined Network (SDN). The IDVR protocol selects the optimal route based on its current location, destination location, and the maximum of the minimum average throughput of SCSR.

In the second part, a problem occurs when the control overhead messages increase due to periodically forwarding of CM HELLO (CMHELLO) messages between the CMs and the CH, and when the CH periodically broadcasts an CH ADvertiSement (CHADS) messages to declare itself to the CMs. Hence, minimizing control overhead messages in any cluster environment is an essential goal to use the network resources efficiently. Therefore, we propose two algorithms: First, a Control Overhead Reduction Algorithm (CORA) which aims to reduce the control overhead messages in a clustered topology, by developing a new mechanism for calculating the optimal number of CMHELLO messages. Second, an Enhanced version of CORA (ECORA) which aims to reduce the CHADS messages that broadcasted by the CHs, by proposing a CHADS prediction algorithm that enables the CH to predict the period of time for broadcasting the CHADS messages.

In the third part, the frequent CH election mainly increases the clustered control overhead messages, which yields to consume high amount of available network resources. High clustered control overhead messages is considered as main problem that negatively impacts the network performance. In this part, we concentrate on the reduction of CH election control overhead messages. Therefore, we propose a new Passive CH election avoidance (PCHEA) protocol that aims to optimize the number of CH election process. In PCHEA protocol, each CH selects another CH based on specific information already stored in its memory, without requiring to trigger the election function. The CH sends to the CMs the next CH identification and its activation time. Also, we propose a CH Routing (CHR) protocol that aims to reduce the number of relayed CHs between any pair of vehicles. In CHR protocol, the CH selects the second adjacent CH among all CH located within its transmission range. The PCHEA protocol and CHR protocol significantly reduce the number of CH elected and increase the average throughput in a bidirectional highway scenario, respectively.

Finally, the proposed protocols are evaluated using SUMO version 0.28.0 traffic generator and MATLAB version R2016b. We compare the performance of the proposed protocols with other protocols in the literature, in different scenarios and in terms of different performance metrics.

Titre traduit

Amélioration de la performance du protocole de routage VANET basé sur les clusters

Résumé traduit

Le protocole Vehicular Ad-Hoc NETworks (VANETs) a considérablement attiré l’attention ces dernières années, en raison de ses caractéristiques uniques, qui sont différentes du protocole Mobile Ad-Hoc NETworks (MANET), notamment le changement de topologie rapide, l’échec fréquent de liaison et la mobilité élevée des véhicules. La mobilité élevée dans VANET provoque des changements de topologie élevés et, par la suite, entraîne un contrôle excessif et des défaillances de liaison fréquentes. Habituellement, les techniques de clustering ont été utilisées comme principale solution pour réduire les messages de contrôle dans VANET. Dans ces techniques, le réseau est divisé en plusieurs clusters et l’un des membres du cluster (CM) est sélectionné en tant que Cluster Head (CH). Les CH sélectionnés sont responsables de la coordination entre les membres du cluster ainsi que de la communication entre eux. Les techniques du clustering réduiront considérablement les frais généraux de contrôle de routage car elles limitent la communication entre chaque CM et son CH au lieu de la communication entre tous les véhicules dans la topologie de VANET. En utilisant le clustering, seul le CH requiert de trouver l’itinéraire de la destination. Par conséquent, les frais généraux de routage sont proportionnels au nombre de clusters et non au nombre de noeuds. Les objectifs de l’utilisation de clusters sont de minimiser les frais généraux de contrôle et d’augmenter la flexibilité du réseau.

La caractéristique la plus importante pour toute technique de clustering est de créer un cluster stable avec un minimum de contrôle de surcharge du cluster. Dans cette thèse, nous définissons quatre types de contrôle de surcharge du cluster, et ils sont comme suit: le surcharge du cluster généré par la formation et de la maintenance du cluster, les messages de contrôle de surcharge transmis des CM au CH, les messages publicitaires diffuses périodiquement par le CH et le contrôle de surcharge diffusé en raison des processus d’élection du CH. En outre, nous supposons que tous les réseaux VANET sont déjà pré-regroupés (preclustered). Par conséquent, les messages de contrôle de surcharge générés par la formation ou la maintenance du clustering sont éliminés. De plus, les messages de contrôle de surcharge générés par le CM et le CH en raison des processus d’élection de CH produisent toujours des messages de surcharge de contrôle élevés.

Dans la première partie, le problème du protocole Clustered-Based Routing (CBR) dans VANET relie les données reçues au CH instable. La plupart des algorithmes d’élection du CH proposes sélectionnent le CH dans la topologie VANET en considérant plusieurs paramètres, tels que: la mobilité, l’emplacement et le noeud Life-Time (LT). La plupart des techniques de clustering produisent une topologie de VANET regroupée (clustered) instable, car ils n’élisent pas le CH stable. Par conséquent, le cluster qui élit le CH approprié qui ne change pas fréquemment est considéré comme un cluster stable, il améliore également les performances de routage CBR en termes de débit et de délai. Par conséquent, nous proposons le protocole Cluster-Based Life-Time Routing (CBLTR). Le protocole CBLTR vise à augmenter la stabilité du routage et le débit moyen dans un scénario de segment bidirectionnel. Les CH sont sélectionnés en function du maximum LT parmi tous les véhicules situés dans chaque cluster. Nous proposons également le protocole Intersection Dynamic VANET Routing (IDVR). Il vise à augmenter le debit moyen et à réduire le délai dans une topologie de grille. L’Intersection CH (ICH) élue reçoit un ensemble de candidats d’itinéraires les plus courts (SCSR) guidant à la destination souhaitée à partir du réseau défini par logiciel « Software Defined Network » (SDN). Le protocole IDVR sélectionne l’itinéraire optimal en fonction de son emplacement actuel, de son emplacement de destination et du maximum et du minimum du débit moyen de SCSR.

Dans la deuxième partie, un problème se produit lorsque les messages de contrôle de surcharge augmentent en raison de la transmission périodique des messages CM HELLO (CMHELLO) entre les CM et le CH, et lorsque le CH diffuse périodiquement un message CH ADVERTIMENT (CHADS) pour se déclarer CM. Par conséquent, la minimisation des messages de contrôle de surcharge dans n’importe quel environnement de cluster est un objectif essential afin d’utiliser efficacement les ressources du réseau. Par conséquent, nous proposons deux algorithmes: d’abord, l’algorithme de réduction des coûts de contrôle « Control Overhead Reduction Algorithm » (CORA) qui vise à réduire les messages de contrôle de surcharge dans une topologie en cluster, en développant un nouveau mécanisme pour calculer le nombre optimal de messages CMHELLO. Deuxièmement, une version améliorée de CORA (ECORA) visant à réduire les messages CHADS diffusés par les CH, en proposant un algorithme de prediction CHADS qui permet au CH de prévoir la période de diffusion des messages CHADS.

Dans la troisième partie, les élections fréquentes de CH augmentent principalement le contrôle de surcharge du cluster, ce qui mène à consommer beaucoup de ressources du réseau disponibles. Le contrôle élevé de surcharge du cluster est considéré comme le principal problem ayant un impact négatif sur les performances du réseau. Dans cette partie, nous nous concentrons sur la réduction des messages de contrôle de surcharge des élections CH. Par conséquent, nous proposons un nouveau protocole passif de prévention des élections CH « Passive CH election avoidance » (PCHEA) qui vise à optimiser le nombre de processus d’élection de CH. Dans le protocole PCHEA, chaque CH sélectionne un autre CH basé sur des informations spécifiques déjà stockées dans sa mémoire, sans nécessiter de déclencher la fonction électorale. Les CH envoient à ses CM la prochaine identification CH et son temps d’activation. En outre, nous proposons le protocole CH Routing (CHR) qui vise à réduire le nombre de CH retransmis entre chaque paire de véhicules. Dans le protocole CHR, le CH sélectionne le second CH adjacent parmi tous les CH situés dans son intervalle de transmission. Le protocole PCHEA et le protocole CHR réduisent considérablement le nombre de CH élus et augmentent le debit moyen dans un scénario de route bidirectionnelle, respectivement.

Enfin, les protocoles proposés sont évalués à l’aide du générateur de trafic SUMO (version 0.28.0) et de MATLAB (version R2016b). Nous comparons la performance des protocols proposés avec d’autres protocoles dans la littérature pour différents scénarios et en fonction de différentes mesures de performance.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Bibliographie : pages 107-110.
Mots-clés libres:	Réseaux ad hoc de véhicules. Protocoles de routage (Protocoles de réseaux d'ordinateurs) Classification automatique (Statistique) Optimisation mathématique. contrôle, message, MANET, VANET, CM, CH, CBLTR, IDVR, ICH, LT, SCSR, CMHELLO, CHADS, CORA, ECORA, PCHEA, CHR
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Kadoch, Michel
Programme:	Doctorat en génie > Génie
Date de dépôt:	27 mars 2018 18:31
Dernière modification:	27 mars 2018 18:31
URI:	https://espace.etsmtl.ca/id/eprint/2018

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt