Clustering is one of the key technologies in vehicular networks. Constructing and maintaining stable clusters is a challenging task in high mobility environments. DWCM (Distributed and Weighted Clustering based on Mobility Metrics) is proposed in this paper based on the d-hop dominating set of the network. Each vehicle is assigned a priority that describes the cluster relationship. The cluster structure is determined according to the d-hop dominating set, where the vehicles in the d-hop dominating set act as the cluster head nodes. In addition, cluster maintenance handles the cluster structure changes caused by node mobility. The rationality of the proposed algorithm is proven. Simulation results in the NS-2 and VanetMobiSim integrated environment demonstrate the performance advantages.
ehicular networks are one of the most promising extensions in future wireless and mobile communication systems, aiming to provide efficient V2V (Vehicle-to-Vehicle) and V2I (Vehicle-to-Infrastructure) communications for road safety, traffic efficiency, and infotainment applications
. Vehicles can use direct, multi-hop, or cluster-based transmission strategies to exchange data with other vehicles or the network infrastructure access points
In a cluster-based transmission strategy, vehicles are organized into multiple clusters. A representative (i.e., a cluster head) is selected for each cluster. The cluster head receives data packets from its cluster members and then relays the packets outside (and vice versa)
. For V2I communication, the clustering strategy can efficiently decrease request/data congestion at the access points in the network infrastructure
. For V2V communication, the clustering strategy can provide a layered architecture to enhance the network scalability
Clustering for MANETs (Mobile Ad-hoc Networks) has attracted considerable research interest
. However, the clustering schemes in traditional MANETs may not be suitable for VANETs (Vehicular Ad-hoc Networks) because of their specific requirements
. Some of VANETs’ notable features should be considered, such as high mobility, the variable density of the VANET nodes, and temporal and spatial dependency in mobility metrics, etc.
. Constructing and maintaining stable clusters in high mobility environments is crucial for communication continuity. Therefore, clustering is indeed an important aspect in a vehicular network.
The motivation of this paper originates from the following two aspects. First, most existing schemes focus on 1-hop clustering; however, d-hop clustering is capable of providing improved and reliable performance for VANETs with better cluster stability and lower cluster dynamics
. Second, mobility-based cluster head selection methods are considered crucial for clustering in VANETs
because of their resilience in handling the nodes’ mobility variation
Based on the above observations, a d-hop dominating set based clustering algorithm, DWCM (Distributed and Weighted Clustering based on Mobility Metrics), is proposed in this paper. The goal of DWCM is to provide an optimal clustering scheme, adaptive to group mobility feature and with enhanced stability. To catch the group mobility feature, each vehicle is weighted with a priority that defines the cluster relationship between this vehicle and its neighbors.
Based on the d-hop dominating set problem in graph theory, a distributed approach for cluster formation and cluster head selection is designed where vehicles in the d-hop dominating set are selected as the cluster head nodes. In addition, cluster maintenance handles the cluster structure changes caused by node mobility; thus, maintaining cluster stability without incurring tremendous overhead. Simulations are conducted in the NS-2 and VanetMobiSim integrated environment. DWCM presents high stability in cluster head lifetime and re-affiliation times, as well as high scalability in the number of clusters.
The rest of this paper is organized as follows. Related work is reviewed in Section 2. Section 3 describes the network model with assumptions. Section 4 introduces the proposed DWCM clustering approach in detail. Section 5 illustrates the performance using simulation results, and is followed by conclusions in Section 6.
2. Related Work
Clustering schemes in traditional MANETs might not be suitable for VANETs because of VANETs’ unique characteristics
. The following features should be considered when designing clustering schemes
(1) Vehicular networks show obvious high mobility feature, which incurs frequent topology changes and makes stability the primary design objective in clustering.
(2) Traffic in VANETs presents unique temporal and spatial distributions, rather than the random distributions often used in MANETs. Different traffic states result in a variable vehicle density, e.g., a sparse distribution of vehicles in suburban areas and a dense distribution in congested areas.
(3) Adjacent vehicles show spatial dependency in their mobility metrics, i.e., consistency in the moving direction and similarity in velocity and acceleration. This is because a vehicle’s movement pattern can be influenced by, and thus correlated with, vehicles in its neighborhood.
In recent years, more effort has been applied toward efficient clustering in vehicular networks. Based on the distance in hops from an ordinary cluster member node to its cluster head, clustering approaches can be classified as 1-hop clustering or d-hop clustering. Most existing approaches are designed to form 1-hop clusters
. Only a few considered d-hop clustering algorithms
. In fact, multi-hop communication is undoubtedly a prevalent scenario in vehicular networks, which makes d-hop clustering a natural choice, with better cluster stability and low cluster dynamics
Cluster size is another factor that should be considered. In
, the authors defined the cluster size measured in geographical distance between a cluster member node and the cluster head node for better radio efficiency and throughput. In d-hop clustering, the cluster size can be defined in hops from a cluster member node to its cluster head. Such a cluster size should be determined by considering two factors. On one hand, a larger cluster size means fewer clusters, which can reduce network maintenance and control overhead. On the other hand, a network diameter limitation in hops
should be considered for efficient multi-hop communication. In addition, clustering that is adaptive to node mobility patterns is believed to have better stability.
Several d-hop clustering schemes in MANETs have also been proposed
. However, the schemes in
did not consider node mobility patterns. In
, a load-balancing clustering scheme that focuses on cluster maintenance was proposed, with the goal of limiting the number of mobile nodes in each cluster so the clusters have similar sizes. Although
had mobility-aware features, the special mobility characteristics in VANETs were not considered. In VANETs—aside from simple mobility metrics, such as moving direction, velocity, and acceleration—more abstract metrics, e.g., mobility dependency, should be defined for an efficient clustering approach
. However, existing works lack conformance with the inherent nature of vehicular networks, such as multi-hop communications and mobility dependency between vehicles. Designing a d-hop clustering algorithm that explores the natural group mobility patterns presented by spatial dependency is a meaningful objective.
Existing schemes use different methods for selecting cluster heads
. Methods based on node characteristics use particular node features for cluster head selection, e.g., node ID
, node degree
, or use the bus node as the cluster head. In mobility-based methods, some mobility and position information is used for cluster head selection. In prediction-based methods, cluster head selection is often performed based on a prediction of link duration.
Among these different schemes, mobility-based methods are considered key for clustering in VANETs
. For example, relative mobility deduced from the received signal strength
, vehicle velocity and position acquired from GPS (Global Positioning System) devices
, and destination information acquired from GPS devices
can be used in cluster head selection. Mobility-based methods are considered to be most appropriate for VANETs because of their resilience in handling node mobility variation
3. Network Model and Assumptions
In this paper, the topology of a vehicular network is modeled as an undirected graph
is the set of vertexes, and each vertex represents a vehicle in the network. If two vehicles are in direct transmission range of each other, there is an edge between them. Thus,
V × V
is the set of edges, and each edge represents a link between vehicles. DWCM depends on the d-hop dominating set to form d-hop clusters. Each vertex is either in the dominating set, or has a path of at most d hops to a vertex in the dominating set. The vertexes in the d-hop dominating set act as cluster heads, whereas the others behave as cluster member nodes.
In this study, the application of the graph theory DS (Dominating Set) problem is motivated by
, where the DS problem provides a promising solution for topology control in MANETs for constructing an efficient network backbone. However, these approaches cannot be applied directly to clustering in vehicular networks because of their different requirements and assumptions.
Topology control in MANETs has unique requirements. For example, the dominating set is often required to be connected and have minimum nodes in the backbone or the shortest path between dominators; thus, the minimum or approximate minimal CDS (Connected Dominating Set) problem is a good choice for describing such approaches. If d-hop clusters are required, the problem evolves to d-hop CDS. In addition, when expecting load balancing or path redundancy features, a k-DS (k-Dominating Set) should be found, where every vertex not in DS has at least k neighboring vertexes in DS.
With regard to optimization objectives, some important factors in MANETs are unsuitable for vehicular networks. For example, energy efficiency is a critical issue for MANETs but meaningless for vehicular networks because the vehicles’ batteries recharge during their journey. In addition, vehicle mobility characteristics, along with location information conveniently acquired from GPS devices, should be considered for cluster head selection.
For convenience, the notations used in the rest of this paper are summarized in
4. Proposed DWCM Clustering Algorithm
- 4.1 d-Hop Dominating Set
As mentioned in Section 3, the network topology is modeled as a graph
), and the d-hop dominating set problem in graph theory is adopted here as a basic approach. Formally, the problem can be defined as:
Definition 1 (d-hop neighborhood)
: The d-hop neighborhood of vertex
is the set of all vertexes within
>1) hops from vertex
Definition 2 (d-hop dominating set)
: For a graph
, a set of vertexes
is called a d-hop dominating set if every vertex is either in
or in the d-hop neighborhood of a vertex in
Previous studies on MANET topology control have proven that finding the minimum d-hop dominating set in such a network topology is an NP-complete problem
. Therefore, suboptimal solution which is the calculation of the minimal d-hop dominating set, should be used to approximate the minimum dominating set problem. In addition, because every node can only acquire the local topology information in vehicular networks, a distributed solution is a natural choice instead of a centralized solution. Based on the above observations, a distributed solution for a d-hop dominating set, based on local topology information, is proposed in this paper. The detailed algorithm is introduced in Section 4.2.
In addition to finding the d-hop dominating set, another important problem is defining the principle in dominating node selection. Each node is assigned a priority, used to evaluate the suitability of a node to act as a cluster head. Depending on different optimization objectives and network environments, the factors involved in the priority calculation could be node identification
, node degree, residual battery power
, travel time, node speed or speed deviation
, and even the integrated result of multiple factors based on a weighted sum or other methods.
As mentioned before, stability is the primary objective in clustering research. Such stability is the result of either less mobility or group mobility (a node and all its neighboring nodes moving in the same direction at approximately the same speed)
. For vehicular networks with high mobility, it is undoubtedly a good choice to explore the priority definition that can well describe the group mobility relationship of a node with its surrounding neighbors. Therefore, the node priority is defined as a cluster relationship in this paper. A detailed introduction is given in Section 4.2.
- 4.2 Cluster Formation and Cluster Head Selection
Cluster formation is the procedure for finding the d-hop dominating set, where the nodes in the dominating set will be selected as the cluster heads. The rules for cluster head selection are introduced first with a correctness proof. The node priority definition is presented thereafter, followed by a distributed approach for cluster formation and cluster head selection.
- 4.2.1 Rules for cluster head selection
In the proposed DWCM clustering approach, every node communicates with its neighbors to obtain some necessary information. Using this information, a priority value is calculated for each node. Thereafter, a node decides to become a cluster head if either of the following criteria is satisfied:
: The node has the highest priority in its d-hop neighborhood;
: The node has the highest priority in the d-hop neighborhood of another node in its d-hop neighborhood.
Each node uses the above rules to determine its role in clustering. If the node satisfies either rule, it behaves as the cluster head node. Otherwise, it acts as an ordinary cluster member node. After all nodes perform such determination, the d-hop dominating set is found based on
) derived from the network topology. The correctness of this approach can be proven as follows.
. The set of cluster heads selected by the DWCM algorithm constructs a d-hop dominating set.
: Given the definition of a d-hop dominating set, a node is either a dominator itself (i.e., in the dominating set) or is a d-hop neighbor of a dominating node. This means, for every node
, it satisfies either:
According to the two rules used by a node to determine whether it is in the d-hop dominating set, the following two cases should be considered:
Case 1: When a node
has the highest priority in its d-hop neighborhood (i.e.,
), it becomes a cluster head because of
, and acts as a dominator, i.e.,
. At this time, node
belongs to the d-hop dominating set and satisfies
. The nodes in the d-hop neighborhood of node
Case 2: For other nodes, node ,
, can select the node with the highest priority in its d-hop neighborhood as the cluster head based on
. At this time, the selected cluster head node belongs to the d-hop dominating set and satisfies
is in the d-hop neighborhood of the selected cluster head, and thus satisfies
. Obviously, a conclusion can be reached that a d-hop dominating set is found after the cluster formation procedure is performed. □
- 4.2.2 Node priority definition
As mentioned in Section 4.1, when defining node priority, we hope to use the spatial dependency in the mobility metrics between adjacent vehicles. Such a priority describes the group mobility characteristics and natural cluster relationships, and thus becomes a reasonable choice for the criteria in cluster head selection.
Based on our previous work in
, node priority is defined as the cluster relationship between this node and its neighbors, which is derived from some basic mobility metrics. Given that vehicles can obtain location information conveniently through GPS devices, such a location is represented by its Cartesian coordinates at every time interval
. Then, the linear displacement of node
can be denoted as:
denote the increase in linear distance of the X and Y coordinates.
Thus, the average velocity of node
can be calculated as:
Similarly, the average acceleration of node
can be defined as:
is the velocity variation over
Based on the above basic mobility metrics, the relative mobility metrics between two adjacent vehicles can be defined. For example, the relative velocity of nodes
is defined as:
is the vehicles’ maximum speed or the upper speed limit of the road.
Similarly, the relative acceleration of nodes
is defined as:
is the vehicles’ maximum acceleration.
Then, the SD (Spatial Dependency) of nodes
can be defined considering both relative velocity and acceleration, as shown in Equation (6). The inclusion of the relative acceleration is necessary for a better description of the future relative position of the two nodes.
For a vehicle
neighbors, its CR (Cluster Relationship) can be defined as its average total spatial dependency on all its
neighbors, and calculated as:
Based on the above analysis, a node priority is defined using its
, and then used in the clustering formation and cluster head selection algorithm. A detailed communication procedure for performing the distributed approach is introduced in Section 4.2.3.
- 4.2.3 Distributed approach
The distributed approach for cluster formation and cluster head selection is illustrated in
. For each node
is executed to determine its state in the cluster, with
as the parameter to indicate the maximum cluster radius in hops. Each node is initialized to the
state. Each node maintains two lists for its d-hop neighbors: (1)
, which contains the mobility information of its d-hop neighbors; (2)
, which records <
> for every node in its d-hop neighborhood, where
represents the node ID of the neighbor with the highest priority in
’s d-hop neighborhood.
are empty. Then, each node exchanges mobility information within its d-hop neighborhood to fill the
, calculates its priority value accordingly, and exchanges priorities within its d-hop neighborhood. In the period of flooding
, each node sends its <
> within its d-hop neighborhood and fills in the
accordingly. Then, the node can use
to determine whether it satisfies
. If so, the node can be nominated as the cluster head.
- 4.3 Clustering Maintenance
After cluster formation, the cluster structure may suffer frequent changes because of node mobility, e.g., nodes joining or leaving the cluster or a cluster head leaving or failing. Cluster maintenance is another important clustering procedure for handling cluster structure changes, aiming to maintain cluster stability without incurring tremendous overhead.
Some studies have addressed clustering maintenance simply by re-clustering. Obviously, in re-clustering, the cluster head re-election and the necessary information exchange between vehicles result in high computation costs and communication overhead. Therefore, cluster maintenance in DWCM follows a principle similar to
, where each node continuously senses the surrounding topology and reacts accordingly with necessary adjustments based on the existing cluster structure.
The detailed cluster maintenance operations are shown in
. Each node executes
to adjust its state in the cluster to adapt to topology changes. DWCM can address the following maintenance situations:
Cluster head contention: Nodeu, nominated as a cluster head throughAlgorithm 1. performs this operation to contend with another cluster headv, whenuandvare within d-hop distance. The node with higher priority wins the contention and acts as the cluster head, whereas the other gives up its role as cluster head and changes its state toNon_Clustered.
Cluster gateway discovery: If a cluster member can hear messages from more than one cluster head, it behaves as a cluster gateway and changes its state accordingly.
Isolated node discovery: If a cluster head loses all its cluster members, or a cluster member or gateway does not hear from its cluster head and its upstream node during a predefined interval, it becomes an isolated node. Then, its state should be changed toNon_Clustered.
Joining a new cluster: ANon_Clusterednodeuselects a suitable clustered neighborvand joinsv’s cluster. The criteria for selectingvinclude: 1) nodevhas the highest SD value inu’s neighborhood, and this value is higher than a predefined threshold; 2) the moving direction ofuandvis almost the same, i.e., below a threshold. This is used to avoid joining a cluster that moves in the opposite direction; and 3) the distance fromutovis less than theClusterMaxHopconstraint.
5. Simulation Results
Simulations were conducted in the network simulator NS-2
to verify the effectiveness and performance of the proposed DWCM clustering algorithm. Because there are no predefined mobility models for vehicle movement, VanetMobiSim
was used as the microscopic traffic generator to provide traffic simulation data that describe realistic vehicle traffic. A common framework was designed in NS-2 to implement the clustering algorithms. The simulation parameters are defined in
The proposed DWCM clustering algorithm and some classical approaches (including Lowest-ID, Highest-degree, MOBIC, and MobDHop), were implemented in NS-2. Lowest-ID
selects cluster heads with the lowest node ID and easily causes re-clustering when an un-clustered node with a lower ID reaches a cluster head’s range. Highest-degree
uses the local highest node degree as the attribute for cluster head selection. However, it still has the same problem as Lowest-ID, where re-clustering occurs frequently.
proposes an aggregate local mobility metric for the cluster formation process, such that mobile nodes with a lower speed than their neighbors have the chance to become cluster heads. MobDHop
forms variable diameter clusters based on the node mobility pattern in MANETs. It introduces a new metric for measuring the distance variation between nodes over time to estimate the relative mobility of two nodes. The multi-hop clustering schemes of MobDHop and the proposed DWCM are evaluated with 2-hop performance (i.e.,
= 2) as a tradeoff between low cluster dynamics and complexity. It is practical to acquire 2-hop information with acceptable complexity, while providing enhanced stability compared with 1-hop clustering.
These clustering approaches were simulated under a series of similar configurations. For performance evaluation, the following performance metrics were chosen:
Firstly, the performance of Lowest-ID based 1-hop clustering, Highest-degree based 1-hop clustering, MOBIC based 1-hop clustering, MobDHop based 2-hop clustering, and DWCM based 2-hop clustering was simulated when the transmission range of the vehicles varied from 50 m to 300 m with a fixed N = 125 and S = 20 m/s.
shows the cluster stability of the above approaches when varying the transmission range. From the results, we can see that DWCM outperforms the other approaches in both cluster head lifetime and re-affiliation times.
Mean cluster head lifetime: Also known as cluster lifetime, this refers to the average time duration of all the nodes acting as cluster heads during the entire simulation. This is an important metric for cluster stability.
Mean re-affiliation times: The mean times of a node (cluster head or member) leaving one cluster and joining another. A lower value reduces bandwidth consumption during message exchanges for member updates.
Number of clusters: The total number of clusters formed in the network during simulation time. This is a metric for the scalability of the clustering approaches.
Cluster head lifetime and re-affiliation times vs. transmission range
As shown in
(a), in terms of mean cluster head lifetime, DWCM, MobDHop, and MOBIC show obvious performance advantages compared with Lowest-ID and Highest-Degree. This is because DWCM, MobDHop, and MOBIC use relative mobility metric related parameters in cluster formation and cluster head selection. Such parameters can describe the natural group mobility feature and help select more suitable cluster head nodes; thus, improving the cluster lifetime.
Both MobDHop and MOBIC estimate the distance from a node to its neighbor based on the measured received signal strength from that particular neighbor. MobDHop performs better than MOBIC because it uses the standard deviation of the distance variation based on a series of continuous measurements to capture the group mobility, whereas MOBIC only uses a pair of consecutive measurements. DWCM can achieve better performance because more relative mobility metrics, e.g., relative direction, relative velocity, and relative acceleration, are used to define the cluster relationship.
(b) shows that DWCM performs obviously better than the other approaches in terms of mean re-affiliation times because it considers the relative moving direction between different nodes in cluster formation and maintenance operations; thus, it avoids joining a cluster that moves in the opposite direction.
Then, the performance of Lowest-ID based 1-hop clustering, Highest-degree based 1-hop clustering, MOBIC based 1-hop clustering, MobDHop based 2-hop clustering, and DWCM based 2-hop clustering was simulated when the maximumspeed of the vehicles varied from 10 m/s to 30 m/s with a fixed N = 125 and T
= 200 m. Such simulations are used to investigate the effect of vehicle speed on cluster performance.
illustrates the mean cluster head lifetime and mean re-affiliation times with varying maximum vehicle speed in
(b), respectively. We can see performance results similar to those shown in
Cluster head lifetime and re-affiliation times vs. speed
(b) show the stability performance of Lowest-ID based 1-hop clustering, Highest-degree based 1-hop clustering, MOBIC based 1-hop clustering, MobDHop based 2-hop clustering, and DWCMbased 2-hop clustering when the number of vehicles varies from 50 to 75 with a fixed S = 20 m/s and T
= 200 m. The clustering algorithms that consider mobility metrics reveal more obvious performance advantages as the number of vehicles increases. This is because the spatial dependency between the vehicles rises with the number of vehicles, thus improving the cluster stability.
Cluster head lifetime and re-affiliation times vs. the number of vehicles
(c) illustrate the cluster numbers of different approaches for various values of transmission range, vehicle speed, and number of vehicles. These figures show that multi-hop clustering approaches (e.g., MobDHop and DWCM) form obviously fewer clusters than 1-hop clustering approaches (e.g., Lowest-ID, Highest-Degree, and MOBIC) in the simulation. A smaller cluster number is desirable because the delay and overhead can be reduced in cluster-based hierarchical routing. Thus, multi-hop clustering is a more reasonable choice for large-scale vehicular networks.
Cluster number when the transmission range, speed, and number of vehicles vary
We also note the difference between the simulation results in this paper and the performance data in other research papers. It seems that the same algorithm shows worse performance in our simulation. Such a deviation is caused by the mobility models used in the simulation. In this study, VanetMobiSim was used as the microscopic traffic generator to provide more realistic traffic simulation data. The IDM-LC (Intelligent Driver Model with Lane Change) model was used in the simulations. IDM-LC has the functions of IM (Intersection Management) and LC (Lane Change). The IM function induces congestion at intersections. Therefore, the cluster heads and members are more likely to disconnect from each other; thus, resulting in more cluster dismissals, joining new clusters, and re-clustering. The cluster head lifetime decreases, whereas the re-affiliation times increase accordingly. The LC function permits overtaking behaviors, which decrease the mobility dependency between vehicles, and thus degrade the performance of clustering algorithms based on mobility metrics.
Experiments were also conducted to investigate the effects of the cluster radius in hops (i.e., the value of
) on clustering performance.
(c) show the clustering performance of DWCM for mean cluster head lifetime, mean re-affiliation times, and number of clusters, respectively, when
= 2, 3, and 4 hops with a fixed N = 125 and T
= 200 m, with the maximum speed varying from 10 m/s to 30 m/s. Although a clustering performance improvement (i.e., increase in cluster head lifetime, decrease in re-affiliation times, and decrease in number of clusters) can be observed when we increase the cluster radius, the performance benefit is rather limited and will shrink with a larger
Effects of d value on clustering performance
As the optimality of a clustering algorithm is defined as being able to form as few stable clusters as possible at a reasonable overhead
, the overhead introduced by a larger
value should also be considered. For DWCM, the message overhead will increase with a larger number of hops because the vehicles’ mobility information is disseminated within the d-hop range. The message overhead of the cluster formation procedure in the worst case can be as high as
). When entering the cluster maintenance procedure, the message overhead for each topology change can be described as
is the average number of members in a cluster. Therefore, for practical feasibility, the choice of
should consider the tradeoff between low cluster dynamics and overhead.
In addition, when considering practical applications, different city and rural scenarios can affect clustering performance. As observed in the simulation, cluster stability is affected by vehicle density, speed, and wireless transmission range. In city scenarios, the vehicle density is higher, whereas the speed is lower, compared with rural scenarios. In addition, the node priority definition in this paper is based on the group mobility features in VANETs. The spatial dependency in mobility metrics between adjacent vehicles in one road segment is more obvious in city scenarios than in rural ones. Therefore, in general, DWCM will perform better in city scenarios than in rural scenarios.
However, DWCM performance in city scenarios might vary depending on the different road layouts. For example, in a scenario with a dense deployment of intersections and traffic signals, the dynamics of the clusters increase because vehicles often join or leave the clusters; thus, incurring large cluster maintenance overhead. Another case is city expressways, where vehicles move within a long segment to maintain the stable group mobility feature. DWCM is expected to have better performance in such a scenario.
6. Conclusions and Future Work
In this study, DWCM, a distributed and weighted d-hop clustering method based on mobility metrics, was proposed. The goal of DWCM is to construct and maintain stable multi-hop clusters in vehicular networks. A weighted undirected graph was used as the network model. Each vertex in this graph was assigned a priority that described the group mobility feature in the vehicular network. A d-hop dominating set was found for cluster head nomination and the correctness of this algorithm was proven. In addition, cluster maintenance was used to handle the cluster structure changes, including cluster head contention, cluster gateway discovery, isolated node discovery, and joining a new cluster. The simulation results in the NS-2 and VanetMobiSim integrated environment showed that DWCM outperformed other classical clustering approaches in terms of cluster stability, with longer cluster head lifetimes and fewer re-affiliation times. In addition, d-hop clustering in DWCM forms a smaller number of clusters with high scalability. It is notable that recent work
has explored the topology characteristics based on large-scale realistic vehicle mobility traces. A good clustering algorithm should be capable of identifying and adapting to the inherent group mobility patterns of a temporally evolving topology. Designing such a clustering algorithm by employing the complex network theory and statistical physics theory will be our ongoing and future work.
Yan Shi received her Ph. D. degree from Beijing University of Posts and Telecommunications (BUPT), China, in 2007. She is currently a research staff of the State Key Laboratory of Networking and Switching Technology. Her current research interests include network architecture evolution, protocol design and performance optimization of future networks and mobile computing, especially mobility management technology.
Xiang Xu received his B. Sc. degree from Beihua University in 2014 and is working towards the M. Sc. degree in State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT) in China. His current research interests include vehicular networks and mobile Internet.
Changkai Lu received his B. Sc. degree from Shandong Agricultural University in 2011 and is working towards the M. Sc. degree in State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT) in China. His current research interests include vehicular networks and mobile Internet.
Shanzhi Chen received his Ph. D. degree from Beijing University of Posts and Telecommunications (BUPT), China, in 1997. He joined Datang Telecom Technology & Industry Group in 1994, and has been serving as CTO since 2008. He was a member of the steering expert group on information technology of the 863 Program of China from 1999 to 2011. He is the director of State Key Laboratory of Wireless Mobile Communications, and the board member of Semiconductor Manufacturing International Corporation (SMIC). He has made great contributions to TD-SCDMA 3G industrialization and TD-LTE-advanced 4G standardization. He received State Science and Technology Progress Award of China in 2001 and 2012. His current research interests include wireless mobile communications, IoT and emergency communications.
Al-Doori M. M.
Al-Bayatti A. H.
Zedan H. A.
“A comprehensive survey on vehicular Ad Hoc network,”
Journal of Network and Computer Applications
DOI : 10.1016/j.jnca.2013.02.036
“Vehicular networking: a survey and tutorial on requirements, architectures, challenges, standards and solutions,”
IEEE Communications Surveys & Tutorials
DOI : 10.1109/SURV.2011.061411.00019
Leung V. C. M.
Mcleod R. D.
Wong V. W. S.
“Vehicular telematics over heterogeneous wireless networks: A survey,”
DOI : 10.1016/j.comcom.2009.12.010
“Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks,”
IEEE Transactions on Vehicular Technology
DOI : 10.1109/TVT.2007.907233
“Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction,”
DOI : 10.1016/j.comnet.2008.01.018
Bali R. S.
Rodrigues J. J. P. C.
“Clustering in vehicular Ad Hoc networks: taxonomy, challenges and solutions,”
DOI : 10.1016/j.vehcom.2014.05.004
Yu J. Y.
Chong P. H. J.
“A survey of clustering schemes for mobile ad hoc networks,”
IEEE Communications Surveys & Tutorials
DOI : 10.1109/COMST.2005.1423333
“Applicability of position-based routing for VANET in high-ways and urban environment,”
Journal of Network and Computer Applications
DOI : 10.1016/j.jnca.2012.03.009
Zhou M. C.
“A position-based clustering technique for Ad Hoc Intervehicle communication,”
IEEE Transactions on Systems, Man and Cybernetics - Part C: Applications and Reviews
DOI : 10.1109/TSMCC.2007.913917
“Dynamic clustering-based adaptive mobile gateway management in integrated VANET-3G heterogeneous wireless networks,”
IEEE Journal on Selected Areas in Communications
DOI : 10.1109/JSAC.2011.110306
“Mobility-based clustering in VANETs using Affinity Propagation,”
in Proc. of IEEE Global Telecommunications Conference 2009
November 30-December 4, 2009
Er I. I.
Seah W. K. G.
“Performance analysis of mobility-based d-hop (MobDHop) clustering algorithm for mobile ad hoc networks,”
DOI : 10.1016/j.comnet.2005.12.013
Pazzi R. W.
“A novel multi-hop clustering scheme for vehicular ad-hoc networks,”
in Proc. of 9th ACM International Symposium on Mobility Management and Wireless Access
October 31-November 4, 2011
“A novel cluster-based protocol for topology discovery in vehicular ad hoc network,”
in Proc. of ACM 3rd International Conference on Ambient Systems, Networks and Technologies
August 27-29, 2012
“Robust clustering for connected vehicles using local network criticality,”
in Proc. of IEEE Conference on Communications 2012
June 10-15, 2012
“Fast randomized algorithm for 2-hops clustering in vehicular ad-hoc networks,”
Ad Hoc Networks
DOI : 10.1016/j.adhoc.2012.02.006
“Inter-vehicle communication: technical issues on vehicle control application,”
IEEE Communications Magazine
DOI : 10.1109/35.544327
Nocetti F. G.
Gonzalez J. S.
“Connectivity based k-hop clustering in wireless networks,”
in Proc. of IEEE 35th Annual Hawaii International Conference on System Sciences
January 7-10, 2002
Amis A. D.
Vuong T. H. P.
Huynh D. T.
“Max-min d-cluster formation in wireless ad hoc networks,”
in Proc. of IEEE 19th Conference on Computer Communications
March 26-30, 2000
“An adaptive multihop clustering scheme for highly mobile ad hoc networks,”
in Proc. of 6th International Symposium on Autonomous Decentralized Systems
April 9-11, 2003
McDonald A. B.
Znati T. F.
“Design and performance of a distributed dynamic clustering algorithm for ad-hoc networks,”
in Proc. of 34th Annual Simulation Symposium
April 22-26, 2001
Ng J. M.
“A distributed group mobility adaptive clustering algorithm for mobile ad hoc networks,”
in Proc. of IEEE International Conference on Communications 2008
May 19-23, 2008
Wieselthier J. E.
Baker D. J.
“A design concept for reliable mobile radio networks with frequency hopping signaling,”
in Proc. of the IEEE
vol. 75, no. 1
Tsai J. T. C.
“Multiuser, Mobile, Multimedia Radio Network,”
DOI : 10.1007/BF01200845
Little T. D. C.
“A mobility based metric for clustering in mobile ad hoc networks,”
in Proc. of IEEE 21st International Conference on Distributed Computing Systems Workshop
April 16-19, 2001
“A new aggregate local mobility (ALM) clustering algorithm for VANETs,”
in Proc. of IEEE International Conference on Communications 2010
May 23-27, 2010
“Mobility-based clustering in VANETs using affinity propagation,”
in Proc. of IEEE Global Telecommunications Conference 2009
November 30-December 4, 2009
Morales M. M. C.
Hong C. S.
Bang Y. C.
“An adaptable mobility-aware clustering algorithm in vehicular networks,”
in Proc. of IEEE 13th Asia-Pacific Network Operations and Management Symposium
September 21-23, 2011
Garcia-Luna-Aceves J. J.
“Topology management in ad hoc networks,”
in Proc. of the 4th ACM international symposium on Mobile ad hoc networking & computing
June 1-3, 2003
Yang H. Y.
Lin C. H.
Tsai M. J.
“Distributed algorithm for efficient construction and maintenance of connected k-hop dominating sets in mobile ad-hoc networks,”
IEEE Transactions on Mobile Computing
DOI : 10.1109/TMC.2007.70736
Wolterink W. K.
“A content-based routing protocol for mobile ad-hoc networks using a distributed connected k-hop dominating set as a backbone,”
University of Twente
Anitha V. S.
Sebastian M. P.
“(k,r)-Dominating set-based, weighted and adaptive clustering algorithms for mobile ad hoc networks,”
DOI : 10.1049/iet-com.2010.0370
Chen S. Z.
Zou L. H.
“A mobility metrics based dynamic clustering algorithm for VANETs,”
in Proc. of IET International Conference on Communication Technology and Application 2011
October 14-16, 2011
“Distributed clustering for ad hoc networks,”
in Proc. of 4th International Symposium on Parallel Architectures, Algorithms, and Networks
June 23-25, 1999
“The ns Manual,”
“VanetMobiSim - Vehicular Ad hoc Network mobility extension to the CanuMobiSim framework,”
“On the instantaneous topology of a large-scale urban vehicular network: the cologne case,”
in Proc. of the 14th ACM international symposium on Mobile ad hoc networking and computing
July 29-August 1, 2013