Project topics and materials
Get Complete Project Material File(s) Now! »
Vehicular Ad-hoc Networks (VANETs)
Vehicular networks are considered as a specialization of Mobile Ad-hoc Networks (MANETs), and their main difference is that nodes’ movements are restricted to the limited mobility pattern of vehicles, in roads and lanes. In VANETs, every vehicle is defined as a node in the network and is equipped with a communications unit called an On-Board Unit (OBU) and an Application Unit (AU). The main function of the OBU is to exchange information with other vehicles or with access points which are placed by the side of the road. Those stationary access points are called Road Side Units (RSU). The term AU refers to any device that can serve to show information to the user (mainly the vehicle’s on-board computer and the driver’s smartphone) [51]. We can separate the elements that compose a VANET in three areas (see Figure 2.1)
In the vehicle: The node’s OBU and AU exchange information internally, either through wired or wireless connections. The OBU acts as a gateway, connecting this small sub-network to the rest of the VANET;
In the air: The wireless connection between different nodes, or between nodes and the infrastructure, can use different parts of the radio spectrum, and a variety of protocols. The most well-known radio access technologies (RAT) are IEEE 802.11p for ad-hoc networking, and LTE for cellular communications. However, there are other examples that have been considered in the literature, such as WiFi, 3G cellular protocols, or WiMAX;
The infrastructure: Access networks and equipment supporting access to the internet: RSUs and cellular base stations (BS) that connect the VANET to the backbone network.
The basics of clustering
There are no strict definitions in clustering algorithms, and each one can present its own variations in its structure or procedures. However, there are certain trends that can be observed in the vast majority of the existing literature. The main principle is converting an disorganized set of nodes in a clustered network by assigning each of them a specific role. The basic set of roles consists of:
Cluster Head (CH): one single leader of a cluster, usually performing special functions such as information aggregation or distribution;
Cluster Members (CM): regular node that belongs to the cluster;
Gateway: a CM that has the special responsibility of providing inter-cluster communication (the CH can take this role). The usual cluster formation procedure, as depicted in Figure 3.1, is to elect the Cluster Heads in first place, according to a specific metric which is normally different for mostly every clustering algorithm, and then letting the isolated nodes associate to its nearest CH, becoming its Cluster Members, and eventually choosing a gateway (when it is not the CH) for communicating with other Cluster Heads.
For this process to take place, control information needs to be exchanged between nodes. In every algorithm, nodes transmit specific signalling and metrics. Some of the most usual choices are IDs, neighbour lists, speed and direction (for mobile networks), or battery level. The Cluster Head election will in most cases be a decision taken by the node itself, upon observation of its own metrics and the ones it receives from its neighbours. This step is a fundamental part of each clustering algorithm, differentiating one from the others. Different methods will be presented throughout the rest of this chapter. The exchange of control information can take place with different degrees of synchronization (either tight synchronization, loose synchronization or no synchronization at all). The usual approach is the regular broadcast of beacons, commonly known as Hello packets, which can contain different types of information depending on the algorithm, but they will normally contain at least the node’s ID, and its current position if the nodes are mobile.
The timeline of clustering algorithms
In the history of clustering algorithms, there were a few initial proposals which were very influential at the time, and helped shape the theoretical basis of the domain. Even though they have all been outperformed by newer generations of clustering algorithms, with more complex techniques and/or focusing on more specific problems, mostly every new proposal is based on some parts of the set of rules and ideas that compose the legacy of these first algorithms. We will now present a brief description of these algorithms since, because of their simplicity, they can help the reader understand the fundamentals of clustering in practice, for a better comprehension of the design choices we have made in our own proposal. The Lowest-ID algorithm [37] published in 1987 was the first proposal for clustered networks. The idea behind it is very simple: every node is assigned an unique identifier (ID), which is the only available metric for CH election. The algorithm is executed in periods called epochs, and each of them is subdivided in two periods, one for transmitting and one for receiving control information, in a way that resembles Time Division Multiple Access (TDMA). A pre-requirement for this to work is that nodes are synchronized, in order for their transmission and reception periods to be the same, and in these periods, every node transmits in an orderly manner in function of its ID. Each node broadcasts its own ID, along with the list of nodes that it can hear.
If a node only hears nodes with a higher ID than its own, then this node is a Cluster Head (this self-election is then announced);
The lowest-ID node that one node can hear becomes its cluster head;
If a node can hear two or more cluster heads becomes a gateway node.
The Highest-Degree algorithm [62] [42] gets to create larger clusters, thus reducing the number of clusters in the network, by changing the metric for cluster head election. While in Lowest-ID the metric had no correlation with any efficiency metric, analyzing the number of neighbors (degree) of a node, and picking those with the highest number of neighbors as Cluster Heads, certainly improves the results in terms of cluster size and robustness of the link between the CH and the other members. In this algorithm, nodes share their IDs, their list of neighbours and their current status during a broadcast period. At the end of this period every node knows who their neighbors are, and it also knows the degree of its neighbors. The rules are:
A node that hasn’t yet elected its “parent” Cluster Head is defined as an uncovered node.
A node that has elected its Custer Head is a covered node.
A node is (self-)elected as Cluster Head if it has the highest degree among its uncovered neighbors
In case of a tie, the lowest ID criteria is adopted
A covered node cannot become Cluster Head.
Table of contents :
1 Introduction
1 Context and motivation
2 Problem
3 Proposed solution and main contributions
4 Overview
2 Intelligent Transportation Systems – Vehicular Networks
1 Introduction
2 Vehicular Ad-hoc Networks (VANETs)
3 Standardization
3.1 IEEE Standards – WAVE
3.2 ETSI Standards
4 Applications
4.1 Road security
4.2 Traffic management
4.3 Infotainment
5 Conclusion
3 Clustering algorithms – State of the art
1 Introduction
2 The basics of clustering
2.1 Maintenance
2.2 Cluster size
2.3 Cluster head election
2.4 Overlapping and interference
2.5 Centralization
2.6 Costs and benefits
3 The timeline of clustering algorithms
4 Clustering algorithms for vehicular networks
4.1 Metrics
4.2 Theoretical performance limits
4.3 Classification
4.4 Scenarios
4.5 Multi-hop vs. Single-hop clustering algorithms
4.6 Hybrid vehicular networks
5 Conclusion
4 Simulation framework
1 The Veins simulation framework
1.1 SUMO: Urban mobility simulator
1.2 OMNeT++: Network simulator
2 Scenario elements
3 Protocol stack
4 Path loss and interference model
5 Maps and vehicular flow generation
6 Hardware setup and execution time
7 Conclusion
5 Base Clustering Algorithm
1 Motivation, objectives and contribution
2 Problem formulation
3 Cluster Head Selection Algorithms
3.1 Cluster Head Self-Appointment
3.2 BS-based Selection
4 Simulation results
4.1 Simulation settings
4.2 CH Self-selection improvements
4.3 Maximum number of hops vs. packet loss rate
4.4 Maximum number of hops vs. cluster size
4.5 Global compression ratio
5 Conclusions
6 Self-Adaptive Clustering Algorithm
1 Motivation and objective
2 The Self-Adaptive Clustering Algorithm
2.1 Network Model
2.2 Self-Adaptive Algorithm
3 Simulation
3.1 Simulation settings
3.2 Simulation results
4 Conclusions
7 Distributive Justice: Fairness-Aware Clustering Algorithm
1 Introduction
2 Distribution of access costs to the cellular network
2.1 The payer
2.2 The billing method
2.3 The access restrictions
2.4 Retained model
3 Fairness-Aware Clustering Algorithm
3.1 Common-Pool Resource (CPR) Problems
3.2 A Theory of Distributive Justice
3.3 The Algorithm
4 Simulation
4.1 Simulation configuration
4.2 Simulation results
5 Conclusions
8 Conclusion
Bibliography
