Transcript Distributed Clustering in Vehicular Networks

Toward Strongly Connected
Clustering Structure in
Vehicular Ad hoc Networks
Zaydoun Y. Rawshdeh, Syed Masud Mahmud
Electrical and Computer Engineering Department
Wayne State University, Detroit, MI, USA
Presented by:
Sanaz Khakpour
Master of Computer Science Student
7/17/2015
1
Objectives
• Use clustering techniques in order to decrease the dynamic
topology of VANETs as much as possible.
• Cluster the nodes with most similar mobility pattern using
direction, location, and speed.
• Partitioning the network to minimum number of clusters.
• Using a multi-metric election technique to choose the best
cluster head.
• Increase cluster stability considering changes in the network
topology which have direct effect on stability.
7/17/2015
2
Identifying Candidate Cluster Member
• Degree of speed difference is a key feature to build stable
clusters.
• The position information (sent in periodic messages) of vehicles
is being used to build neighbourhood relationship (rneighbour).
• Nodal degree is the total number of r-neighbours of a node.
• Neighbour nodes moving in the same direction are supposed
to be candidate cluster members (CCM).
• Neighbours are classified to SN (r-distance, same direction,
close speed) and UN.
• All SN which do not belong to other clusters are CCM.
7/17/2015
3
Identifying Candidate Cluster Member
•
The speed of vehicles is assumed to be random variable (Normal
distribution 𝜇 and variance σ2 ). Probability density function (pdf):
𝑓𝑣 𝑣 =
•
1
𝜎 2𝜋
The speed difference between vehicles (∆V) follows normal
distribution as follow:
𝑓∆𝑣 ∆𝑣 =
•
𝑒
−(𝑣−𝜇)2
2𝜎2
1
𝜎∆𝑣 2𝜋
𝑒
−(∆𝑣−𝜇∆𝑣)2
2𝜎2
The probability that speed difference between two vehicles is in
the threshold (∆𝑉𝑡ℎ ):
𝑓∆𝑣 (-∆𝑣𝑡ℎ < ∆𝑣 < ∆𝑣𝑡ℎ )=
1
𝜎∆𝑣 2𝜋
∆𝑣𝑡ℎ −(∆𝑣−𝜇∆𝑣)
2𝜎2
𝑒
−∆𝑣𝑡ℎ
2
• To avoid high variation in the number of SN, threshold is
assumed to be a function of deviation, such as ∆𝑣𝑡ℎ = 𝛽𝜎.
7/17/2015
4
Protocol Structure
• Control channel: is being used to send periodic messages and
gain information about neighbours. (Transmission range R).
• Service channel: is used to create cluster and send intracluster messages and cluster management. (Transmission
range r < R).
• Because R=4r, vehicles can obtain complete information
about their neighbours (can be beyond cluster boundaries)
• Any vehicle can understand if its speed is less than all its nonclustered neighbours in R distance range. That vehicle is
supposed to start cluster formation.
7/17/2015
5
Cluster Radius
• DSRC (Dedicated Short-Range Communications) is a multichannel interface with various transmission ranges.
• Neighbourhood definition depends on the used channels.
• Vehicles u and v are neighbours in control channel’s
perspective. But u and w are neighbours from the perspective
of both channels.
7/17/2015
6
Cluster Formation
• Each vehicle keeps a list of 2-r neighbours at time t (Γ(t)).
• Γ(t) is divided into Γ(t)_G and Γ(t)_L which are vehicles with
greater and lower speeds respectively.
• The vehicle with lowest speed among its neighbours starts
cluster formation. It is called cluster originating vehicle (COV).
• COV sends its ID to all Γ(t)_G as temporary cluster ID. All non
clustered members set the cluster ID.
• Vehicles calculate their suitability to be a CH and announce it
if their value is higher than previously received values.
Suitability value is compared with only r-neighbour members
of Γ(t)_G of COV.
7/17/2015
7
Cluster Rules
• Vehicles that can’t connect to the cluster stay non-clustered
(default state) and start cluster formation process again.
• A node joins cluster if its relative speed to CH is in the
threshold.
• The members should stay in r-distance range. Otherwise, they
will lose their membership.
• Two clusters can merge if:
 The distance between CHs are less than r.
 The difference between average speed and both CH’s
speed is in a threshold.
7/17/2015
8
Cluster Head Selection
• Suitability function is used to verify eligibility of a node to be
CH.
•
nodes with closer distance to their neighbours and closer
relative speed to average speed of neighbours are supposed
to have higher connectivity degree.
• CCM of COV is Γ(t)_G including {𝑛1 , 𝑛2 , … , 𝑛𝑘 }, connectivity
degree (d) of node 𝑛i is calculated as follow:
𝑘
𝑑𝑖 =
{𝑑𝑖𝑠(𝑛i
𝑝𝑜𝑠
, 𝑛j 𝑝𝑜𝑠 ) < 𝑟}
𝑗=1,𝑗≠𝑖
𝑛i
𝑝𝑜𝑠
, 𝑛j 𝑝𝑜𝑠 are current position of nodes i and j
𝑑𝑖𝑠(𝑛i
𝑝𝑜𝑠
, 𝑛j 𝑝𝑜𝑠 ) is distance between nodes i and j
7/17/2015
9
Cluster Head Selection
• Then normalized mean distance of a node 𝑛1 to its
d1 neighbours is (𝜇𝑝 is mean position and 𝜎𝑝 is standard
deviation):
𝑃𝑛𝑜𝑟𝑚 =
𝑛i
𝑝𝑜𝑠
−𝜇𝑝
𝜎𝑝
• Value of 𝑃𝑛𝑜𝑟𝑚 indicates the distance of node from centre of
its neighbours.
• The suitability of node to be CH is expressed as follow:
S=d*𝑒 −𝛼𝑤
w= 𝑃𝑛𝑜𝑟𝑚 + 𝑉𝑛𝑜𝑟𝑚 and 0< 𝛼 ≤ 1
7/17/2015
10
Simulation Results
• Vehicles enter a multi-lane highway and move for 10 km.
• Vehicles can only change lane if there is no obstacle,
otherwise they will slow down and stay behind the slower
vehicle in front of them.
• Cluster radius (r) is 200m and control channel range (R=4r) is
800 m.
𝑙𝑖𝑓𝑒
• Cluster lifetime (Ci
)is being evaluated which is directly
dependant on CH lifetime:
Ci,mean 𝑙𝑖𝑓𝑒 =
1
𝐿
𝑙𝑖𝑓𝑒
𝐿
C
𝑖=1 i
,
L: total number of clusters
Ci,mean 𝑙𝑖𝑓𝑒 : mean cluster lifetime
7/17/2015
11
Simulation Results
7/17/2015
12
Questions
• What parameters are used for calculating mobility
metric?
• What are Γ(t)_G and Γ(t)_L in cluster formation
process?
• What is he paper’s most important objective?
7/17/2015
13