---
# System prepended metadata

title: 'Report 1: Theory for Cluster Establishment'

---

# Report 1: Theory for Cluster Establishment

## Vehicular Network

2 main components:

- OBE (on-board equipment): connect to wireless network and in-vehicle network
- RSE (road-base epuipment): connect moving vehicles, connect to core network

2 main types: V2V, V2I, both use short range communication freq, within ad-hoc network

## VANET: Vehicular Ad-hoc Network

a kind of large-scale ad-hoc network that turns movings cars into wireless nodes

characteristics:

- high mobility of nodes
- wide range relatvie spd
- real time nature of application

## Dedicated short range communication technique

A technology that enables highly secure, high-speed direct communication between vehicles and the surrounding infrastructure, without involving any cellular infrastructure.

75MHz bandwidth (5.850 - 5.925 GHz) in our algorithm, it is divided into 7 channels:

- 1 control channel: longer transmission range R, CH to CH communication, broadcast periodic mess, gather inf about neighborhood
- 6 service channels: shorter transmission range r, intra-cluster communication

each vehicle utilizes one control channel and one service channel

## Clustering Algorithm Description

Two main phase: Cluster Formation and Cluster Maintenance

### Cluster Formation

- vehicles broadcast their state to all other node in and gather information of their neighhood

- vehicles classify its 2r-stable neighbors and non-stable neighbors (stable = same direction and relative spd &leq; a threshold)

- slowest vehicle sends a cluster formation request &rarr; cluster originating vehicle (COV), only its 2r-stable neighbors can join the cluster formation process

- all its 2r-stable neighbors set its CID to ID of COV, then calculate suitability to become CH and time waiting to announce as a CH (T_wait)

- if T_wait expires and dont receive any FormCluster mess &rarr; broadcass FormCluster mess

- else, quit cluster head competition

- only r-stable neighbors of winner which also are 2r-stable neighbors of COV change its state to CM and its CID to ID of winner

### Cluster Maintenance

Events that trigger the maintenance procedure:

- *Joining a cluster*: 
    - case 1: only have one CH: CH accept new CM if it satisfies stable condition

    - case 2: 2+ CHs: the vehicle calculates the greatest remaining time (RT) for each cluster, and it will join the cluster with highest RT

- *Leaving a cluster*: can join another cluster, or form a new cluster or change state to standalone

- *Cluster merging*: CH with less number of members gives up its CH and become CM of the biger one, other members also join if they re within new CH range or calculate RT and choose, the left forming new cluster or turn into standalone state

## Implementation

classes:

- V2vControlApplication: extends Application built-in class
    - Send(): create appropriate type of header and fill it

    - HandleRead(): read and process diff types of header

    - IsStable()
    - IsSlowest()
    - MergeCheck()
    - SuitabilityCheck()
    - UpdateNeighborList()

4 header classes

- V2vClusterInfoHeader
- V2vInitiateClusterHeader
- V2vFormClusterHeader
- V2vIncidentHeader: this is for construction scenario in evaluation

## Evaluation

Evaluate through scenarios

- Basic configuration params: mean velocity, velocity deviation (they introduce statical distrib of velocity as normal distrib), lane distance, number of vehicles, simulation time

- WAVE configuration params: Tx Power, Tx Gain, Rx Gain

&rarr; 3 scenarios for WAVE config with 3 diff values of number of vehicles

Values that are evaluated:

- The number of Formation messages (including periodic mess, cluster init mess, form cluster mess)

- The number of state changes (stability of cluster)

- Average delay: when a CM receives incident mess, send a direct mess to CH and CH broadcast the event to all members (worst case), if CH or standalone receive incident mess, then broadcast

Some other evaluation criteria from the original article of the algorithm:

- Average cluster lifetime: from when a vehicle becomes CH to when it performs cluster merging

- Number of clusters (Cluster formation rate): good algorithm reduces the rate

- Overhead for clustering: includes overhead due to periodic mess, overhead due to cluster setup, overhead due to cluster maintenance (these calculated from theory)