Wireless Personal Communications

https://doi.org/10.1007/s11277-020-07578-7

DCA‑DS: A Distributed Clustering Algorithm Based

on Dominating Set for Internet of Vehicles

Oussama Senouci1,2 · Zibouda Aliouat2 · Saad Harous3

© Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract
In this paper, we propose a new Distributed Clustering Algorithm Based on Dominating
Set (DS) for Internet of Vehicles, called DCA-DS. To construct the DS, DCA-DS algo-
rithm introduces a new parameter, called node span, which represents the number of the
node neighbours that are not unclustered, including the node itself. DCA-DS algorithm
is based on a simple heuristic method that uses a greedy strategy, where the node having
the largest span is included in the DS, therefore it acts as new CH and all its neighbours
become Cluster Members (CMs). This process repeats iteratively until there are no unclus-
tered nodes left. Moreover, the node, which can hear two CHs or more, will act as Cluster
Gateway (CG). Furthermore, DCA-DS algorithm takes care of the maintenance phase to
keep clusters stability and structure. The proposed approach is implemented in NS-2 net-
work simulator and VanetMobiSim mobility simulator to evaluate its performance.

Keywords VANET · IoV · Clustering · Dominating set

1 Introduction

The great success of the Internet of Things has led to the evolution of conventional Vehicu-
lar Ad hoc NETwork (VANET) towards a new paradigm of the intelligent transportation
systems, called Internet of Vehicle (IoV) [1]. The difference between these two paradigms
is essentially in terms of devices, communication technologies and applications available
for the vehicle. In VANET, the vehicle is seen as a mobile node, which can communicate
with other vehicles and infrastructures by exchanging messages. On the other hand, each
vehicle in the IoV paradigm plays the role of an intelligent mobile object with a complex
and powerful sensors-system, communication technologies and connectivity to infrastruc-
ture, other vehicles and Internet [2].

* Saad Harous
harous@uaeu.ac.ae
1
Computer Science Department, Mohamed El Bachir El Ibrahimi University, Bordj Bou Arreridj,
Algeria
2
Laboratory LRSD, Computer Science Department, Ferhat Abbas University, Setif 1, Setif, Algeria
3
College of Information Technology, United Arab Emirates University, Al‑Ain, UAE

13
Vol.:(0123456789)
 O. Senouci et al.

Despite the fact that IoV paradigm provides many advantages, it also suffers from cer-
tain challenges. One of the very important challenges is the integration of all the hetero-
geneous components in a single system [3]. Another challenge is the growing number of
vehicles and other objects connected to the IoV network [4]. Consequently, there is a huge
amount of data (big data), which requires particular processing and storage strategies. Fur-
thermore, the IoV paradigm is faced with numerous deployment issues, such as security
issue, reliability of inter-vehicle communications and large number of collisions produced
by the simultaneous access of vehicles to the channel. In addition, IoV technology provides
heterogeneous wireless access technologies, such as WiFi, WiMAX, cellular and satellite
communications. This heterogeneity requires special components and additional costs [5].
Given all of the above issues, researchers have recently utilized several strategies for
different ad hoc networks. Clustering is one of the important strategies used to improve
overall ad hoc networks performance. Generally, clustering aims to partition the nodes of
network into groups, called clusters [6]. In each cluster there is a node, which plays the
role of leader, called Cluster Head (CH), which takes charge of managing the cluster and
ensuring coordination between the members of cluster. Recently, considerable research has
explored clustering for IoV network to improve their performances for different purposes
and applications, such as data routing, data dissemination, channel access management,
security, Quality of Service (QoS) and topology discovery [7]. However, these researchs
suffer from several challenges. The main challenge is the stability and structure of clus-
ters, particularly in a very dynamic environment [8]. Moreover, compared with other ad
hoc networks, the vehicular network has specific requirements related to mobility and new
functionalities of the IoV technology [9].
In this paper, we propose a new Distributed Clustering Algorithm based on Dominat-
ing Set (DCA-DS) for IoV environment. To construct the DS, the proposed algorithm
introduces a new parameter, called node span, which represents the number of the node
neighbours, which are not unclustered, including the node itself. The dominating set is
constructed based on a simple method that uses a greedy procedure, where the node having
the largest span is included in the DS, therefore it acts as new CH and all its neighbours
become Cluster Members (CMs). This process repeats iteratively until there are no unclus-
tered nodes left. Moreover, the node, which can hear two CHs or more, will act as Cluster
Gateway (CG). Furthermore, DCA-DS algorithm takes care of the maintenance phase to
keep clusters stability and structure. We simulate our proposed algorithm using the net-
work simulator NS-2 and VanetMobiSim integrated environment. Simulation’s results
show that the proposed algorithm DCA-DS outperforms N-hop protocol [10] in term of
CH lifetime, CM lifetime, number of clusters and clustering overhead.
The rest of this paper is organized as follows. Section 2 presents the related work. Sec-
tion 3 introduces the proposed algorithm in detail. Section 4 provides the performance
evaluation of the proposed approach. Finally, a conclusion is presented in Sect. 5.

2 Related Work

Recently, clustering is widely used in vehicular network and in particular IoV paradigm to
overcome their different challenges and improve their performance. Consequently, several
clustering algorithms, based on dominating set problem, have been proposed in the litera-
ture. In the rest of this section, we shed light on the most important ones.

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

As for clustering in Mobile Ad hoc Networks (MANETs), even for VANET, Cokuslu
et al. [11], presented a new Connected Dominating Set (CDS) based algorithm, which
adopts the Wu and Lis [12] algorithm. The contribution provides significant modifications
by taking into account other parameters, such as nodes degrees during the marking process.
Also, it uses other heuristic strategies to construct the dominating set, which represents the
cluster heads.
A new Connected Dominating Set (CDS) based clustering approach to prevent the
broadcast storm problem in vehicular networks is presented in Cha et al. [13]. The pro-
posed approach considers two parameters: nodes mobility and degree. Then it matches the
dynamic topology of vehicular network. Moreover, the proposed approach utilizes a typical
information dissemination strategy suitable for different purposes, such as emergency and
traffic information. Furthermore, this work introduces a new virtual core-network, which
can be constructed by searching for a CDS in the network.
The work of Yan et al. [14] introduced a new Distributed and Weighted Clustering
algorithm based on Mobility metrics (DWCM), where the authors designed a distributed
approach for cluster formation and cluster heads election phases based on dominating
set problem. The algorithm works by prioritizing vehicles in k-hop dominating set to be
selected as new CHs. Moreover, DWCM algorithm proposed a new maintenance strategy,
which makes it possible to confront the unstable topology of VANET environment due to
the high mobility of vehicles. Therefore, the main goal of DWCM solution is to construct
and maintain stable k-hop clusters, with reasonable network costs.
In Togou et al. [15], the authors introduced a new Stable CDS-based Routing Protocol
(SCRP) suitable for urban area. It is based on a distributed geographic location source for-
warding strategy, which considers the vehicular network topology for selecting the data
routing paths with low latency. To reach this goal, SCRP algorithm constructs stable core
networks over the road segments based on two parameters: nodes’ speed and their spa-
tial distribution. These core networks are connected at intersections via special gateway
nodes that ensure an up-to-date vehicular network topology and keep track of the expected
delay for data routing on the road segments. Based on this information, the SCRAP scheme
assigns a weight for each road segment. Thus, the road segments with the lowest weights
are selected to form the data routing paths.
Senouci et al. [16] presented a new Multi-hop Clustering Approach over Vehicle-to-
Internet, namely MCA-V2I. This scheme assumes that every vehicle can connect to
the Internet via a special infrastructure called a Road Side Unit Gateway. Based on this
assumption, the vehicle can obtain and share different information about its multi-hop
neighbours to run the clustering process. The latter is performed using the Breadth-First
Search (BFS) strategy for traversing the graph, including a new parameter, called mobility
rate, which is calculated according to various mobility parameters, such as relative veloc-
ity, nodes’ degree and link stability.
Chinnasamy et al. [17] proposed a new Minimum connected dominating set-based
RSU allocation for smart-Cloud vehicles in VANET. To begin the allocation process,
every smart-Cloud vehicle sends periodic beacon packet (coordinates) to the nearest RSU.
This latter in turn, periodically, tracks the affiliation of the smart-Cloud vehicle whether it
belongs to the CDS. Therefore, every Smart-Cloud vehicle in the CDS uses a shorter wait-
ing period and retransmits the current coordinates again to the same RSU. After the expira-
tion of the time period, a smart-Cloud vehicle must transmit its new coordinates to address
the next RSU connectivity and appearance of new neighbours.
Tran et al. [18] developed an efficient connected dominating set clustering based rout-
ing protocol with dynamic channel selection (CRD) in multi-channel cognitive radio

13
 O. Senouci et al.

MANETs. The proposed protocol aims to improve the general performance of clustering
even if the node moves with very high speed. Therefore, the CRD protocol is applicable
also in VANET and IoV environments. To perform the clustering process, the authors pro-
pose a new CDS selection strategy and clustering algorithm to form clusters. Then, the
protocol chooses a set of intermediate nodes for later use in the routing phase. To establish
the route between source and destination passing by the intermediate nodes, a new sending
channel based focus region selection (CFS) algorithm is adopted dynamically.
In Senouci et al. [19], the authors introduced a new Efficient Weight based Clustering
Algorithm for IoV, called WECA-MR. This clustering algorithm aims to improve the clus-
ters’ stability, structure and communication overhead. To perform the clustering process,
WECA-MR scheme combined both conventional weighted metrics (node degree, average
distance) and introduced a new metric, called mobility report. This new metric is calcu-
lated based on mobility parameters: relative velocity and acceleration. Furthermore, the
WECA-MR approach improves the clusters’ stability and structure by electing a Backup
CH in addition to the main CH.
Finally, Zhang et al. [10] proposed a new multi-hop clustering algorithm to improve
clusters’ stability. To begin the clustering process, the authors introduced a new mobility
parameter to compute the relative mobility between vehicles in k-hops distance. In this
algorithm, vehicles must identify the aggregate mobility of all k-hops distance neighbours.
As a result, extra control overhead messages are produced within the network, which even-
tually reduces the efficiency and performance of the clustering process.

3 Distributed Dominating Set Clustering Algorithm

3.1 Network Model

The proposed algorithm is suitable for highway areas and developed according to the fol-
lowing assumptions. First, we assume that every vehicle is equipped with a positioning
system, i.e. Global Positioning System (GPS). Second, we have a highway with three lanes
for each road. Finally, the topology of the IoV network is modelled as an undirected graph
G = (V, E), where V is the set of vertices or nodes that represent the vehicles in the net-
work. There is an edge between two vertices, if they are mutually in the transmission cov-
erage area of each other. Therefore, E ⊆ V × V is the set of edges, and every edge is a com-
munication link between two vertices.
Then, we have the following definitions of graph theory that will be used in the pro-
posed algorithm:

1. Dominating set (DS) A dominating set S of a graph G = (V, E) is a subset of nodes S ⊆ V

such that every node in V is either in S or adjacent to at least one node in S [20]. Figure 1
shows an example of dominating set in graph. Each white vertex is adjacent to at least
one red vertex, and it is said that the white vertex is dominating by the red vertex. As a
result, the red nodes (1 and 7) represents the dominating set.
2. Dominator node It is a node that is a member of the dominating set.
3. Dominated node A node dominated by a dominator node.
4. Span of node It is the number of the node neighbours, which are not dominators or
dominated by another dominators, including the node itself.

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

Fig. 1  Example of dominating

set in graph

3.2 Proposed Algorithm

In this section, we propose a new Distributed Clustering Algorithm based on Dominat-

ing Set (DCA-DS) suitable for IoV environment. The dominating set is constructed based
on a simple heuristic method, which uses a greedy procedure. The greedy procedure is a
strategy that follows the heuristic principle of problem solving by making step by step, an
optimum local choice with the aim to find an optimal global solution [21]. Generally, a
greedy strategy does not guarantee an optimal global solution, nevertheless, this heuristic
approach can lead to quickly find locally optimal sub-solutions, which approximate an opti-
mal global solution in a very reasonable time [22]. Therefore, the construction of the DS
in the proposed algorithm is done based on a greedy strategy, where the node having the
largest span is included in the DS (locally optimal sub-solution), therefore it acts as new
CH and all its neighbours become cluster members. This process repeats iteratively until
there are no unclustered nodes left (global solution). Moreover, the node, which can hear
two CHs or more, will act as cluster gateway. Furthermore, DCA-DS algorithm takes care
of the maintenance phase to keep clusters stability and structure.
In this algorithm, a node may be in one of the following three states (colors): white,
black or gray. The meaning of these states is as follows:

• White node It is a node that is not a dominator or is not dominated by any node. Ini-
tially, all nodes are colored white.
• Black node The node is a dominator, i.e., member of DS.
• Gray node A node dominated by a dominator.

3.2.1 Cluster formation

1. To perform the cluster formation phase, the DCA-DS algorithm initially colors all nodes
of the network white (Unclustered Node (UN)).
2. Then, each UN node broadcasts a BEACON message (containing its id, position and
color) to its direct neighbours.
3. Thereafter, every node after receiving the BEACON messages from its neighbours, it
computes its span. Then, it broadcasts a SPAN request (containing its span) to its direct
neighbours.
4. When a node receives the SPAN requests from its neighbours, it compares its span with
all the spans received. If its span is the largest one, the node must announce its election
as new CH and updates its state to CH and its color to black (to join the DS). This CH

13
 O. Senouci et al.

will broadcast an UPDATE(GRAY) request to its neighbours, and wait for their replies
to confirm their membership. Otherwise, the node elects the node that has the maximum
span value as its new CH and waits for its UPDATE(GRAY) request.
5. Each node, after it receives the UPDATE(GRAY) request from the new CH, updates its
state to CM and its color to gray, then it sends a REPLY to the CH to confirm the mem-
bership. At this stage, if a node receives two or more UPDATE(GRAY) requests from
different CHs, it will act as Cluster Gateway (CG).
6. This process continues until there are no white colored nodes left.

Algorithm 1 shows the cluster formation process, where the variable mySPAN holds the cur-
rent span of node i, the array SPANS holds the spans of the neighbours of node i, and the var-
iable color has the current color of node i, and the CHs (DS) is the output of the algorithm.

Figure 2 shows a simple example of cluster formation phase using our algorithm. First,
node 11 is colored black because it has the highest span (5) among all the nodes of the

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

Fig. 2  Example showing cluster formation phase using the DCA-DS algorithm

network. Then, the nodes 2, 3, 6 and 10 are colored in gray since they are in the span of
node 11. Therefore, the first cluster C1 is formed: C1 {CH: 11; CM: 2,3,6,10}.
After that, node 1 is colored black since it has the highest span (4) among the remaining
nodes. Then, its white neighbours 5, 8 and 12 are colored gray. Thus, the second cluster C2
is formed: C2 {CH: 1; CM: 5,8,12}. Finally, node 9 is colored black, and nodes
4 and 7 are colored gray. Therefore, the third cluster C3 is formed: C3 {CH:9; CM:
4,7}. The process ends, because all the nodes are colored either black or gray.

3.2.2 Cluster Maintenance

When the cluster formation phase ends, the clusters structure may suffer frequent changes
because the nature of the corresponding network is characterized with high mobility and
dynamic topology, e.g., clusters overlapping, vehicles joining and leaving cluster. There-
fore, cluster maintenance is an important phase to keep clusters’ structure and stability.
DCA-DS approach addresses the maintenance phase as follow:

13
 O. Senouci et al.

• Clusters merging When two neighbour clusters or more overlap, a cluster merging pro-
cess is triggered. Typically, the merging process ends up in two CHs or more for the
resulting cluster. The CH that has the largest number of members (in its original clus-
ter) acts as new CH for the resulting cluster. The other CHs must change their state to
CM.
• Leaving a cluster If a CH loses communication link with one of its members, or a
cluster member does not hear from its CH, therefore this member becomes an isolated
node. As a result, the CH must delete this member from its cluster member list. This
node changes its state to UN, and can then join another cluster.
• Joining a cluster When an UN node approaches a CH, it sends a join request to this
CH. When the CH receives the join request from this UN node, it must add it immedi-
ately in its member cluster list, and then sends a reply message to this UN node. When
the UN node receives the reply message from the CH, it changes its state to CM.

4 Simulations

In this section, we evaluate the performances of the proposed algorithm DCA-DS using
the Network Simulator NS-2 [23] and the mobility generator VanetMobiSim [24]. Mobility
is simulated on a one-directional highway of 1.5 km length with three lanes. The velocity
varies from 10 to 35 m/s, and the transmission range of the vehicles is set to be 250 m. The
mobility model used is IDM-LC, which is integrated directly into VanetMobiSim, and the
propagation model used is Two-ray Ground. The different simulation parameters are listed
in Table 1. DCA-DS scheme is compared with N-Hop approach [10]. The evaluation of the
clustering algorithms is done on the basis of four performance indicators: CH lifetime, CM
lifetime, number of clusters and clustering overhead.

4.1 CH Lifetime

CH lifetime is an important indicator to interpret the effectiveness of the clustering algo-

rithm. It represents the period, where the vehicle is in a CH state until it shifts into another
state. Figure 3 shows the average CH lifetime of our solution DCA-DS versus N-hop
algorithm under different velocity values. According to Fig. 3, we can make two observa-
tions. Firstly, as the velocity increases, the average CH lifetime decreases for both algo-
rithms, that is due to the high mobility of vehicles, which makes the network topology very
dynamic. Secondly, the average CM lifetime is higher when DCA-DS protocol is used than

Table 1  Simulation parameters Parameter Value

Simulation time 300 s

Simulation area 1500 × 50 m
Transmission range 250 m
Propagation model Two-ray Ground
Mobility model IDM-LC
MAC/PHY protocol 802.11p
Velocity of vehicles 10–35 m/s

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

Fig. 3  Average CH lifetime

when N-hop protocol is used for both high and low velocities. As a result, DCA-DS algo-
rithm outperforms N-hop algorithm in term of CH lifetime by almost 100%.

4.2 CM Lifetime

Figure 4 shows the average CM lifetime when our proposed DCA-DS is used versus when
N-hop algorithm is used under different velocity values. From the result shown in Fig. 4,
we can make two conclusions. First, as the velocity gets higher, the average CM lifetime
changes moderately for both solutions DCA-DS and N-hop, that is due to the high mobil-
ity of vehicles, which makes the network topology very dynamic. Second, the average CM
lifetime of DCA-DS is longer than the one of N-hop for both high and low velocities. As a

Fig. 4  Average CM lifetime

13
 O. Senouci et al.

result, DCA-DS algorithm is better than N-hop algorithm in term of CM lifetime by almost
100% for low velocity and by more than 50% for high velocity.

4.3 Number of Clusters

Figure 5 shows the average number of clusters of our solution DCA-DS versus N-hop
algorithm under different velocity values. According to Fig. 5, we make two conclusions.
Firstly, as the velocity increases, the average number of clusters increases for both algo-
rithms, that is due to the high mobility of vehicles, which makes the network topology very
dynamic. Secondly, the average number of clusters of DCA-DS is lower than the one of
N-hop in both high and low velocities. As a result, DCA-DS algorithm outperforms N-hop
algorithm in term of number of clusters by almost 40% for low velocity and by more than
25% for high velocity.

4.4 Clustering Overhead

Figure 6 shows the average clustering overhead of our algorithm DCA-DS versus N-hop
algorithm under different velocity values. From the result shown in Fig. 6, we can make
two conclusions. On one hand, as the velocity increases, the average clustering overhead
increases for both algorithms, that is due to the high mobility of vehicles, which makes
the network topology very dynamic. On the other hand, the average clustering overhead
of DCA-DS is lower than the one of N-hop in both high and low velocities. Consequently,
DCA-DS algorithm is better than N-hop algorithm in term of clustering overhead by
almost 20% for low velocity and by more than 25% for high velocity.

Fig. 5  Average number of clusters

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

Fig. 6  Average clustering overhead

5 Conclusion

In this paper, we propose a new Distributed Clustering Algorithm based on Dominating Set
(DCA-DS) for IoV environment. To construct the DS, the proposed algorithm introduces
a new parameter, called node span, which represents the number of the node neighbours,
which are not unclustered yet, including the node itself. The dominating set is constructed
based on a simple heuristic method that uses a greedy strategy, where the node having
the largest span is included in the DS. Therefore it acts as new CH and all its neighbours
become cluster members. This process repeats iteratively until there are no unclustered
nodes left. Moreover, the node, which can hear two CHs or more, will act as cluster gate-
way. Furthermore, DCA-DS algorithm takes care of the maintenance phase to keep clusters
stability and structure. We simulate our proposed algorithm using network simulator NS-2
and VanetMobiSim integrated environment. Simulation’s results depict that the proposed
algorithm DCA-DS outperforms N-hop algorithm in term of CH lifetime by almost 100
%, CM lifetime by almost 100 % for low velocity and by more than 50 % for high velocity,
number of clusters by almost 40 % for low velocity and by more than 25 % for high veloc-
ity and clustering overhead by almost 20 % for low velocity and by more than 25 % for
high velocity.

References
1. Sharma, S., & Kaushik, B. (2019). A survey on internet of vehicles: Applications, security issues and
solutions. Vehicular Communications, 20(5), 1–44.
2. Senouci, O., Aliouat, Z., & Harous, S. (2019). A review of routing protocols in internet of vehicles and
their challenges. Sensor Review, 39(1), 58–70.
3. Alouache, L., Nguyen, N., Aliouat, M., & Chelouah, R. (2018). Survey on IoV routing protocols:
Security and network architecture. Sensor Review, 32(2), e3849.
4. Kaiwartya, O., Abdullah, H., Cao, Y., Altameem, A., Prasad, M., Lin, C.-T., et al. (2016). Internet of
vehicles: Motivation, layered architecture network model challenges and future aspects. IEEE Access,
9, 5356–5373.

13
 O. Senouci et al.

5. Ang, L., Seng, K. P., Ijemaru, G. K., & Zungeru, A. M. (2019). Deployment of IoV for smart cities:
Applications, architecture, and challenges. IEEE Access, 7, 6473–6492.
6. Senouci, O., Zibouda, A., & Harous, S. (2017). Survey: Routing protocols in vehicular Ad Hoc
networks. In Proceedings of the second international conference on advanced wireless information,
data, and communication technologies (pp. 8:1-8:6), AWICT ’17, ACM, Paris, France.
7. Cooper, C., Franklin, D., Ros, M., Safaei, F., & Abolhasan, M. (2017). A comparative survey of
VANET clustering techniques. IEEE Communications Surveys Tutorials, 19(1), 657–681.
8. Senouci, O., Harous, S., & Aliouat, Z. (2020). Survey on VANET clustering algorithms: Overview,
taxonomy, challenges, and open research issues. In International Journal of Communication Sys-
tems (pp. e4402).
9. Aadil, F., Ahsan, W., & Rehman, Z. D. (2018). Clustering algorithm for internet of vehicles (IoV)
based on dragonfly optimizer (CAVDO). The Journal of Supercomputing, 74, 4542–4567.
10. Zhang, Z., Boukerche, A., & Pazzi, R. (2011). A novel multi-hop clustering scheme for vehicular
Ad-hoc networks. In Proceedings of the 9th ACM international symposium on mobility manage-
ment and wireless access (pp. 19–29), MobiWac ’11, ACM, New York, NY, USA.
11. Cokuslu, D., Erciyes, K., & Dagdeviren, O. (2006). A dominating set based clustering algorithm
for mobile Ad Hoc networks. Computational Science, 59, 571–578.
12. Wu, J., & Li, H. (2001). A dominating-set-based routing scheme in Ad Hoc wireless networks. Tel-
ecommunication Systems, 18(1), 13–36.
13. Cha, S., Ryu, M., Kim, K., & Jeon, B. (2013). Applying connected dominating set to broadcasting
in vehicular Ad Hoc networks. In 2013 International conference on information science and appli-
cations, ICISA ’13.
14. Shi, Y., Xu, X., Lu, C., & Chen, S. (2016). Distributed and weighted clustering based on d-Hop
dominating set for vehicular networks. KSII Transactions on Internet and Information Systems, 10,
1661–1678.
15. Togou, M. A., Hafid, A., & Khoukhi, L. (2016). SCRP: Stable CDS-based routing protocol for
urban vehicular Ad Hoc networks. IEEE Transactions on Intelligent Transportation Systems, 17(5),
1298–1307.
16. Senouci, O., Aliouat, Z., & Harous, S. (2019). MCA-V2I: A multi-hop clustering approach over
vehicle-to-internet communication for improving VANETs performances. Future Generation Com-
puter Systems, 96, 309–329.
17. Chinnasamy, A., Sivakumar, B., Selvakumari, P., & Suresh, A. (2019). Minimum connected
dominating set based RSU allocation for smartCloud vehicles in VANET. Cluster Computing, 22,
12795–12804.
18. Tran, T., Nguyen, T., & An, B. (2019). An efficient connected dominating set clustering based rout-
ing protocol with dynamic channel selection in cognitive mobile Ad Hoc networks. Electronics,
8(11), 1–26.
19. Senouci, O., Harous, S., & Aliouat, Z. (2018). An efficient weight-based clustering algorithm using
mobility report for IoV. In 2018 9th IEEE annual ubiquitous computing, electronics and mobile
communication conference, UEMCON ’18, IEEE, New York, NY, USA.
20. Jallu, R. K., Prasad, P. R., & Das, G. K. (2017). Distributed construction of connected dominating
set in unit disk graphs. Journal of Parallel and Distributed Computing, 104, 159–166.
21. Fu, D., Hafid, A., Han, L., Yang, Z., & Jhang, S. (2016). A greedy algorithm on constructing the
minimum connected dominating set in wireless network. International Journal of Distributed Sen-
sor Networks, 12, 1–6.
22. Xie, J., Nie, Y., & Liu, W. (2018). A greedy path-based algorithm for traffic assignment. Transpor-
tation Research Record, 2672(48), 36–44.
23. The network simulator NS-2, http://nsnam.isi.edu/nsnam/index.php/Main\_Page. (Accessed on 13
September 2018) [Online].
24. Fiore, M., Harri, J., Filali, F., & Bonnet, C. (2007). Vehicular mobility simulation for VANETs. In
40th annual simulation symposium, ANSS ’07.

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and
institutional affiliations.

13
DCA-DS: A Distributed Clustering Algorithm Based on Dominating…

Oussama Senouci obtained his Ph.D. in computer science from the

University of Ferhat Abbas Sétif-1, Setif, Algeria. In 2019 He is work-
ing in the field of networks and distributed systems. His main research
interests include VANET network.

Zibouda Aliouat obtained her engineering diploma in 1984 and MSc

in 1993 from Constantine University. She received her Ph.D. from
Setif University of Algeria. She was an Assistant at Constantine Uni-
versity from 1985 to 1994. She is currently an Associate Professor in
the Computer Engineering Department at Setif University of Algeria.
Her research interests are in the areas of wireless mobile networks
modeling and simulation, wireless sensor networks and fault tolerance
of embedded systems.

Saad Harous obtained his Ph.D. in computer science from Case West-
ern Reserve University, Cleveland, OH, USA in 1991. He has more
than 30 years of experience in teaching and research in three different
countries: USA, Oman and UAE. He is currently a Professor at the
College of Information Technology, in the United Arab Emirates Uni-
versity. His teaching interests include programming, data structures,
design and analysis of algorithms, operating systems and networks.
His research interests include parallel and distributed computing, P2P
delivery architectures, wireless networks and the use of computers in
education and processing Arabic language. He has published more
than 130 journal and conference papers. He is an IEEE senior
member.

13