Comm.utoronto.ca

Mobility-based Clustering in VANETs using Affinity Propagation Christine Shea, Behnam Hassanabadi and Shahrokh Valaee Department of Electrical and Computer Engineering University of Toronto Toronto, ON, M5S 2E4, Abstract—The recent research in cluster-based MAC and rout- There has been much research on cluster-based VANETs in ing schemes for Vehicle Ad Hoc Networks (VANETs) motivates the recent literature, which has been focused on developing the necessity for a stable VANET clustering algorithm. Due to the cluster-based MAC protocols, as in [3 – 9]. and cluster-based highly mobile nature of VANETs, mobility must play an integralrole in cluster formation. We present a novel, mobility-based routing protocols, as in [10] and [11]. In [4] and [9], the cluster clustering scheme for Vehicle Ad hoc Networks, which utilizes head (CH) takes on a managerial role and facilitates intra- the Affinity Propagation algorithm in a distributed manner.
cluster communication by providing a TDMA schedule to its The proposed algorithm considers typical vehicular mobility cluster members. In [9], adjacent clusters are assigned different during cluster formation to garner clusters with high stability.
CDMA codes to avoid interference between clusters. The work Simulation results confirm the superior performance of theproposed algorithm, when compared to other accepted mobility- in [9] shows a substantial reduction in probability of message based clustering techniques, in terms of average cluster head delivery failure, when compared to traditional 802.11 MAC.
duration, average cluster member duration, and average rate of The recent research discussing cluster-based MACs and cluster head change.
routing schemes for VANETs, present many similar low- maintenance clustering algorithms. In these schemes nodes are required to transmit periodic HELLO beacons to indicate Research in vehicular communications, specifically Vehic- their present state of either Undecided, Cluster Head or Cluster ular Ad Hoc Networks (VANETs), is playing a vital role Member. An undecided node will join the first CH that it hears in the future safety and ease of our roads. VANETs will a HELLO beacon from, and if the node does not hear from a enhance driver safety and reduce traffic deaths and injuries CH within a given time period, it will become a CH itself. In by implementing collision avoidance and warning systems. In these schemes, the first node to declare CH status wins.
addition, VANETs can relieve traffic congestion by providing a Node mobility should play an integral part in cluster cre- driver with live routes that avoid road hazards and bottleneck ation in order to achieve stability. In [4], mobility is addressed areas. The vast sensor network that VANETs will create, is during cluster collision; when two cluster heads come within inciting countless other applications, and making VANETs a range, the winning CH will be the one with both lower relative hot topic in ad hoc networking today.
mobility and closer proximity to its members. Alternatively, The VANET scenario has various difficult challenges for [8] addresses mobility by first classifying nodes into speed communication, many of which can be addressed by a clus- groups, such that nodes will only join a CH of similar velocity.
tered network. VANETs have a highly-mobile environment The above clustering techniques are lacking in cluster stability, with a rapidly changing network topology. By clustering the because they do not attempt to select a stable CH during initial vehicles into groups of similar mobility, the relative mobility cluster head election.
between communicating neighbor nodes can be reduced. Both Although there is not a VANET clustering scheme focused delay-intolerant (e.g. safety messages) and delay-tolerant (e.g.
on cluster stability, there are many mobility-based clustering road/weather information) data will need to be transmitted, ne- techniques for ad hoc networks. A well-known mobility-based cessitating Quality-of-Service (QoS) requirements. Clustering clustering technique is MOBIC [12], which is an extension has been shown to effectively reduce data congestion [1], and of the Lowest-ID algorithm [13]. In Lowest-ID, each node is can support QoS requirements [2]. In addition, traffic jams and assigned a unique ID, and the node with the lowest ID in high node density in urban areas will be inevitable. This leads its two-hop neighborhood is elected to be the cluster head.
to contention and the hidden terminal problem, which are the In MOBIC, an aggregate local mobility metric is the basis performance limiting factors in a dense network and can be for cluster formation instead of node ID. The node with effectively alleviated by a clustered topology.
the smallest variance of relative mobility to its neighbors is This work was supported in part by AUTO21 NCE and MARK IV elected as the cluster head. The relative mobility for a certain Industries - IVHS Division node is estimated by comparing the received power of two consecutive messages from each neighboring node. Cluster all the data points are initialized with the same constant self- head re-election only occurs when two cluster heads move similarity, then all data points are equally likely to become within range of one another for a certain contention interval.
exemplars. By increasing and decreasing this common self- When a cluster member moves out of range of its cluster head, similarity input, the number of clusters produced is increased it joins any current cluster head in its neighborhood, or forms and decreased respectively.
a new cluster.
There are two types of messages passed in this technique.
The previous cluster-based VANET research motivates the The responsibility, r(i, j), is sent from i to candidate exemplar need for a stable VANET clustering scheme. In this paper, j and indicates how well suited j is to be i's exemplar, taking we propose a distributed mobility-based clustering algorithm into account competing potential exemplars. The availability, focused on cluster stability, where stability is defined by a(i, j), is sent from candidate exemplar j back to i, and long cluster head duration, long cluster member duration, indicates j's desire to be an exemplar for i based on supporting and low rate of cluster head change. We achieve this al- feedback from other data points. The self-responsibility, r(i, i) gorithm by utilizing a new data clustering technique called and self-availability, a(i, i), both reflect accumulated evidence Affinity Propagation (AP) [14]. Our clustering scheme will that i is an exemplar.
form clusters with both minimum distance and minimum The update formulas for responsibility and availability are relative velocity between each cluster head and its members.
We assume position information is provided by the vehiclesGPS. We validate our proposed algorithm by comparing it to the mobility-based ad-hoc clustering scheme, MOBIC [12].
r(i, j) ← s(i, j) − a(i, j ) + s(i, j ) j0 s.t.j0 6=j MOBIC is well-established and stability driven, thus providinga good benchmark for our algorithm's success.
The rest of this paper is organized as follows. Section II presents the Affinity Propagation algorithm. Section III a(i, j) ← min 0, r(j, j) + max 0, r(i , j) proposes our distributed, mobility-based, VANET clustering algorithm. Section IV presents our simulation results, andfinally this paper concludes with Section V.
a(j, j) ← max 0, r(i , j) II. AFFINITY PROPAGATION i0 s.t.i0 6=j Thus far, we have discussed clustering from an ad hoc Responsibility and availability message updates must be networking perspective, however clustering is also used in damped to avoid numerical oscillations that will prevent the scientific data analysis, where it aims to process and detect algorithm from converging. This is done by updating new patterns in data. Data clustering is a static, one-shot process messages as follows: mnew = λmold + (1 − λ)mnew, where that searches data for a set of centers, or exemplars, which best λ is a weighting factor between 0 and 1. In AP, the clustering describe the data. In this context, clustering aims to minimize is complete when the messages converge. Another feature the distance between each data point and its assigned exemplar, of the algorithm is the ability to determine when a specific where distance could be Euclidian distance, or any other data point has converged to cluster head status in its given application-specific function. A revolutionary new technique cluster. When a point's self-responsibility plus self-availability for data clustering is the Affinity Propagation (AP) algorithm becomes positive, that point has become the cluster head.
[14], which has been shown to produce clusters in much less Upon convergence, each node i's cluster head is: time, and with much less error than traditional techniques(such as K-means clustering [15]). Here, clustering error refers CHi = arg max {a(i, j) + r(i, j)} to the application-specific distance between each data pointand its assigned exemplar. In Affinity Propagation, data points III. PROPOSED VANET CLUSTERING SCHEME pass messages to one another, which describe the current The proposed clustering technique uses the fundamental affinity that one data point has for choosing another data point idea of Affinity Propagation from a communications per- as its exemplar.
spective and in a distributed manner. We call this algorithm, This algorithm takes an input function of similarities, s(i, j), Affinity PROpagation for VEhiclar networks, (APROVE). In where s(i, j) reflects how well suited data point j is to be our algorithm, each node in the network transmits the respon- the exemplar of data point i. Affinity Propagation aims to sibility and availability messages to its neighbors, and then maximize the similarity s(i, j) for every data point i and makes a decision on clustering independently. This results, in its chosen exemplar j, therefore an application requiring a a distributed algorithm, where every node is only clustering minimization (e.g. Euclidean distance) should have a negative with those in its one-hop neighborhood.
similarity function. Each node i also has a self-similarity, We design a similarity function for our algorithm with the s(i, i), which influences the number of exemplars that are goal of creating stable clusters, and tailored to the VANET identified. Individual data points that are initialized with a environment. Our similarity function, shown below in (5), is a larger self-similarity are more likely to become exemplars. If combination of the negative Euclidean distance between node positions now and the negative Euclidean distance between The broadcast period for availability and responsibility node positions in the future. This is a simple way to consider messages is defined as TM , which we set to 1s in our both node position and node mobility in cluster creation.
simulations. Each node i will calculate its responsibility with each neighbor j using (1). This value is damped with the s(i, j) = − kxi − xjk + kx0i − x0jk previous transmitted responsibility (where λ = 0.5), and stored as r(i, j). Node i then accumulates r(i, j) for each neighbor i + vx,iτf j in the responsibility array, R i, and broadcasts the array in yi + vy,iτf the RESP packet. Each node i will calculate the availability where xi is a vector of node i's current position, and x0 is with each neighbor j using the update equation (2). Node i a vector of node i's predicted future position. The function will store j's damped availability in a(j, i) and accumulates predicts each node i's future position in τf seconds from now, all a(j, i)'s in the availability array, Ai. This array is broadcast based on node i's current velocity vx,i in the x direction and in the AVAIL packet.
velocity v The AVAIL packet also includes the flag CH y,i in the y direction. The Time Future parameter, cnvg . Due to the nature of the AP algorithm, a node's self-responsibility f , can be tuned for different types of mobility.
The self-similarities were initialized to the same value plus self-availability will become positive when it has con- and was set such that the number of clusters produced was verged to cluster head status. For every iteration of the minimized. We gave equal preference to each node, however algorithm, each node i checks for this condition, and then it is possible to assign certain vehicles (such as large trucks) sets the CHcnvg flag accordingly. This flag indicates to i's a higher preference, making them more likely to become the neighbor nodes whether or not they should consider i as cluster head.
a potential cluster head. The responsibility and availabilitybroadcast procedure is outlined in Procedure 2.
A. Message Passing and the Neighbor List Every node i will maintain a neighbor list, N Procedure 2 Broadcast of RESP and AVAIL messages a neighbor list entry, Nj, for every neighbor j. Each neighbor Every TM , each node i will: list entry, Nj contains the following fields: 1) Calculate responsibility, r(i, j) for each neighbor j 2) Update with damping factor: (x, y)j: position vector of node j r(i, j) = (1 − λ)r(i, j)new + λr(i, j)old (vx, vy)j: velocity vector of node j 3) Store responsibilities, r(i, j), in array: Ri s(i, j): similarity for i and j 4) Calculate availability, a(j, i) for each neighbor j a(i, j): last availability received from j 5) Update with damping factor: a(j, i): last availability transmitted to j a(j, i) = (1 − λ)a(j, i)new + λa(j, i)old r(j, i): last responsibility received from j 6) Store availabilities, a(j, i), in array: Ai r(i, j): last responsibility transmitted to j 7) Determine if converged to CH status: cluster head converge flag for node j if r(i, i) + a(i, i) > 0, then set CHcnvg Index of j's current cluster head 8) Broadcast the RESP packet: hRii Time that node j expires 9) Broadcast the AVAIL packet: hAi, CHcnvgi Each node j will periodically broadcast a HELLO beacon containing its ID, position, velocity and current cluster head.
When node i receives a RESP or AVAIL packet from j, The hello broadcast period is defined as TH, where we have it will search for its id in the Rj or Aj array, and if found, used TH = 1s in our simulations. Upon reception of a it reads off its specific responsibility or availability message.
HELLO beacon from node j, node i will calculate its current These message are stored in the received message fields, r(j, i) similarity with j, s(i, j), using (5) and update its neighbor list or a(i, j) of j's neighbor list entry, Nj. If the received packet with the new information. A node only considers neighbors is of AVAIL type, node i will also update the CHcnvg,j field moving in the same direction, and ignores broadcasts from for j according to the CHcnvg flag received. This routine is traffic in the opposite direction. This procedure is outlined in summarized in Procedure 3.
Procedure 1.
Procedure 3 Reception of RESP and AVAIL messages Procedure 1 Broadcast and Reception of Hello Beacons Upon reception of a RESP or AVAIL packet from node j, 1) Every T node i will: H , each node j broadcasts HELLO beacon: hj, (x, y)j, (vx, vy)j, CHji 1) Search for its id, i in the Rj or Aj array.
2) Each receiving neighbor, i, checks if j is traveling in 2) If a message addressed to i is found, update the r(j, i) the same direction or a(i, j) field in the neighbor list entry, Nji 3) If true, i calculates similarity with j, s(i, j) 3) Check if CHcnvg flag is set, and update CHcnvg,j field 4) Node i adds/updates j's neighbor list entry, Nj's: in j's neighbor list entry, Nji hj, (x, y)j, (vx, vy)j, s(i, j), texpire, CHji B. Cluster Formation and Maintenance Highway scenarios were created using the VanetMobiSim Clustering decisions are made periodically with a period of traffic simulator [16], which generates realistic mobility pat- CI called the Clustering Interval. Note that the T terns, including lane changing. The highway was generated period must be small enough to allow the algorithm to con- in a looped formation with a 3km, 3-lane highway moving verge within a CI period. Preliminary simulations show that a in each direction. The vehicles reach their maximum speed neighborhood of 40 nodes can converge in under 10 iterations.
during the main highway pass, and then slow significantly at the turns, creating a realistic pattern with both low and high M of 1s, requires a minimum CI of 10s) density traffic. The highways moving in either direction were Every CI, node i finds its cluster head using (4). However, separated by more than the 250m broadcast range, so that clus- node i only considers its neighbors with the CHcnvg,j flag tering could not occur across them. Our proposed algorithm set, which confirms node j will become a cluster head. In the will not cluster vehicles moving in opposite directions, but event that none of the neighbors have set their CHcnvg,j flag, MOBIC will, which degrades cluster stability. This step was node i becomes its own cluster head.
taken to provide a fair comparison of MOBIC and APROVE.
In between clustering iterations of CI, we perform cluster maintenance. Every TCM (the period of cluster maintenance), A. Clustering Performance Metrics node i purges its neighbor list of old entries by checking the To evaluate the cluster stability and overall performance of texpire fields. After purging, node i checks if its cluster head our algorithm, we use the following metrics: is still in its neighbor list. If the CH has been lost, node i 1) Average Cluster Head Duration: Long cluster head searches through its neighbors for current CHs to join, by duration is important for MAC schemes where the cluster head finding neighbors with CHj = j. The CHcnvg,j flag is not is the central controller and scheduler.
used here because it indicates the potential cluster heads for 2) Average Cluster Member Duration: This metric judges the next round, not the current cluster heads. If multiple CHs the overall stability of the initial clustering.
are found in the neighbor list, node i uses (4) to select the best 3) Average Rate of Cluster Head Change: This metric is one. If node i can not find another neighbor that is currently useful since it takes into account both cluster head duration a CH, it becomes its own cluster head.
and the number of clusters formed.
There are some important notes regarding the passing of 4) Average Number of Clusters: To effectively decrease availability and responsibility messages. Firstly, the messages network contention, fewer clusters is desirable.
are not reset between clustering iterations, which gives mem-ory to the algorithm and provides preference to previous B. Performance Analysis cluster heads. This feedback results in less frequent cluster In the first set of simulations, the maximum velocity of the changes. Secondly, our algorithm does not assume synchro- vehicles was 40m/s (144km/h). The Cluster Interval, CI, was nization, and each vehicle can run it independently of one swept from 10s to 150s and Time Future, τ another. In the asynchronous case, the received availability f , was swept from 0s to 120s. Figure 1 plots the effect of CI and τ and responsibility messages will be at most one period old.
Since these messages are averaged over time and a vehicle's It can be seen from Figures 1a, 1b, and 1c that APROVE's movement over one time period is small, the algorithm's cluster stability far exceeds that of MOBIC. Figure 1d in- performance will not be effected. In the case of a lossy dicates that MOBIC performs better in terms of number channel, messages can be older than one time period, which of formed clusters. However, the cluster change rate, which may cause the algorithm's performance to degrade. In this involves the joint effect of CH duration and the number case, a more reliable MAC (such as [7]) can be used to increase of clusters, proves that APROVE's overall performance is the message reception probability.
superior. Notice that average cluster change rate is proportionalto the number of clusters formed, and inversely proportional IV. SIMULATION RESULTS to the CH duration. From Figure 1c we can see that there is We have implemented the proposed algorithm in NS2, an optimal τf setting for each setting of CI. Based on this which has been highly validated by the networking research plot, a τf of 30s was chosen for future simulations, as it gave community. All simulations were performed with 100 vehicles the best performance for this mobility scenario.
on a highway. Each simulation ran for 500s, however only the By sweeping over different velocities, we compare the clus- last 200s were used for performance metric calculations. This tering performance of APROVE and MOBIC. Using VanetMo- was to ensure that the algorithm had reached a steady state biSim, highway scenarios were generated with approximate before measuring its performance. All of the simulation results maximum velocities of 15, 25, 35, 40, and 50m/s. The perfor- were averaged over 10 different mobility scenarios, and used mance results are displayed in Figure 2. Figure 2d shows that the following timing parameters: TH = TM = TCM = 1s.
MOBIC generates a smaller number of clusters, however, it The 802.11 MAC and the 914MHz Lucent WaveLAN DSSS can be observed from Figures 2a, 2b, and 2c, that APROVE's network card with a radio range of 250m, have been used stability performance far exceeds that of MOBIC. Figure 2c in the NS2 simulations. The MOBIC code was taken from a allows us to judge overall clustering performance, and when legacy version of NS2 provided by [12].
comparing APROVE and MOBIC at a typical highway speed Fig. 1. The impact of τf on cluster performance for different CI settings. Simulations run with 100 nodes and maximum velocity = 40m/s. τf = 0, 10, 30, 50, 70, 90, and 120s, and CI = 10, 30, 60, 90, 120, and 150s. MOBIC's performance is also plotted. (a) The average cluster head duration. (b) The averagecluster member duration. (c) The average rate of cluster head change. (d) The average number of clusters of 40m/s, APROVE shows 300% improvement in average rate of cluster head change. It is also evident that while MOBIC's Motivated by the ample research in cluster-based MACs performance degrades at higher mobility, APROVE's perfor- and routing schemes for VANETs, we have proposed a novel mance degrades at lower mobility. A possible explanation and stable mobility-based clustering algorithm. Our algorithm for this trend is that parameter optimization was done for elects cluster heads periodically, by using affinity propagation 40m/s, thus the timing parameters have been tuned to higher from a communications perspective, and in a distributed man- ner. The algorithm finds clusters that minimize both relative MOBICs lesser stability performance could be caused by mobility and distance from each cluster head to its cluster error in the mobility metric and cluster member suitability.
members. The clusters created are stable and exhibit long The use of received power in the mobility metric can lead average cluster member duration, long average cluster head du- to inaccuracies in the relative mobility calculation due to ration, and low average rate of cluster head change. APROVE's channel fluctuations. In addition, the MOBIC algorithm does high stability makes it a suitable candidate for clustering in a not consider cluster member suitability when forming clusters.
mobile and dynamic environment, such as VANETs.
Although the CH will initially have the lowest relative mobility in its neighborhood, a cluster member with high relative [1] W. Chen and S. Cai, "Ad hoc peer-to-peer network architecture for vehi- mobility will enter and exit the cluster quickly, and will choose cle safety communications," Communications Magazine, IEEE, vol. 43, a new cluster head without regard for the mobility metric.
no. 4, pp. 100–107, April 2005.
CI = 160, τ = 30 CI = 160, τ = 30 CI = 120, τ = 30 CI = 120, τ = 30 Avg. CH Duration (s)
Avg. CM Duration (s)
CI = 160, τ = 30 CI = 160, τ = 30 CI = 120, τ = 30 CI = 120, τ = 30 No. of CH Changes/sec
Avg. Number of Clusters 10
The impact of velocity on cluster performance, comparing APROVE and MOBIC. APROVE is plotted with τf = 30s, and CI = 30, 60, 120, and 160s. Max velocity = 15, 25, 30, 40, and 50m/s. (a) The average cluster head duration. (b) The average cluster member duration. (c) The average rate ofcluster head change. (d) The average number of clusters [2] R. Ramanathan and M. Steenstrup, "Hierarchically-organized, multihop routing in vehicular ad hoc networks," Vehicular Technology Conference, mobile wireless networks for quality-of-service support," Mobile Net- 2007. VTC-2007 Fall. 2007 IEEE 66th, pp. 2169–2173, 30 2007-Oct. 3 works and Applications, vol. 3, no. 1, pp. 101–119, 1998.
[3] L. Bononi and M. Di Felice, "A cross layered mac and clustering scheme [11] R. E. R.A. Santos and N. Seed, "Inter vehicular data exchange between for efficient broadcast in vanets," Mobile Adhoc and Sensor Systems, fast moving road traffic using ad-hoc cluster based location algorithm 2007. MASS 2007. IEEE Internatonal Conference on, pp. 1–8, Oct. 2007.
and 802.11b direct sequence spread spectrum radio," PostGraduate [4] Y. Gunter, B. Wiegel, and H. Grossmann, "Cluster-based medium access Networking Conference, 2003.
scheme for vanets," Intelligent Transportation Systems Conference, [12] P. Basu, N. Khan, and T. Little, "A mobility based metric for clustering 2007. ITSC 2007. IEEE, pp. 343–348, 30 2007-Oct. 3 2007.
in mobile ad hoc networks," Distributed Computing Systems Workshop, [5] Z. Rawashdeh and S. Mahmud, "Media access technique for cluster- 2001 International Conference on, pp. 413–418, Apr 2001.
based vehicular ad hoc networks," Vehicular Technology Conference, [13] C. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," 2008. VTC 2008-Fall. IEEE 68th, pp. 1–5, Sept. 2008.
Selected Areas in Communications, IEEE Journal on, vol. 15, no. 7, pp.
[6] F. Farnoud and S. Valaee, "Repetition-based broadcast in vehicular ad 1265–1275, Sep 1997.
hoc networks in rician channel with capture," April 2008, pp. 1–6.
[14] B. J. Frey and D. Dueck, "Clustering by passing messages between data [7] B. Hassanabadi, L. Zhang, and S. Valaee, "Index coded repetition-based points," Science, vol. 315, pp. 972–976, 2007.
mac in vehicular ad-hoc networks," Jan. 2009, pp. 1–6.
[15] J. B. MacQueen, "Some methods for classification and analysis of [8] O. Kayis and T. Acarman, "Clustering formation for inter-vehicle multivariate observations," in Proc. of the fifth Berkeley Symposium on communication," Intelligent Transportation Systems Conference, 2007. Mathematical Statistics and Probability, L. M. L. Cam and J. Neyman, ITSC 2007. IEEE, pp. 636–641, 30 2007-Oct. 3 2007.
Eds., vol. 1. University of California Press, 1967, pp. 281–297.
[9] H. Su and X. Zhang, "Clustering-based multichannel mac protocols for [16] M. Fiore, J. Harri, F. Filali, and C. Bonnet, "Vehicular mobility simula- qos provisionings over vehicular ad hoc networks," Vehicular Technol- tion for vanets," Simulation Symposium, 2007. ANSS '07. 40th Annual, ogy, IEEE Transactions on, vol. 56, no. 6, pp. 3309–3323, Nov. 2007.
pp. 301–309, March 2007.
[10] B. Wiegel, Y. Gunter, and H. Grossmann, "Cross-layer design for packet

Source: http://www.comm.utoronto.ca/~valaee/Publications/09-Shea-Globecom.pdf